Gate2018 cs Q41

0. Let G be a graph with 100! Vertices, with each vertex labeled by a distinct permutation of the numbers 1, 2, …. 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 + 10z = _________.

Note – Numerical Type question

Answer
Comment
Array

Option : B
Explanation :
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 makes for 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 other vertex 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 x 1 = 109

Forgot your password?

I agree with the Terms.