GATE Computer Science (CS) 2018 Shift 1 Solved Paper

Question : 52 of 65

Marks: +1, -0

Let G be a graph with 100! Vertices, with each vertex labeled by a distinct permutation of the numbers 1, 2, …. 100. There is an edge between vertices u and v if and only if the label of u can be obtained by swapping two adjacent numbers in the label of v. Let y denote the degree of a vertex in G and z denote the number of connected components in G. Then, y z + = 10 __________ .

Your Answer:

Validate

Solution:

The graph has 100! Vertices which each vertex labeled by one of the 100! Permutation.take a vertex whose labeling is say 1,2,3,4, …..,100.
Now it will be connected to all vertices where exactly 2 of the adjacent numbers all swapped.
The two swapped numbers could be (1, 2), (2, 3), (3, 4) …. etc. upto (99, 100) which makesfor 99 edges for each such vertex.
So the graph is a regular graph with each vertex connected to 99 other vertices.
So y = 99
The number of connected components = z = 1 since we can go from any vertex to any othervertex by only swapping 2 adjacent number at a time, many times i.e. there is a path from any vertex to any other vertex.
Graph is connected.
So z = 1
So

y +10z =99+10×1=109

Go to Question:

Prev Question

Next Question