Question

Let G be a graph with 100! vertices, with each vertex labelled 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 + 10z =

• A. 109

Answer 1

The correct option is A 109
The graph has 100! vertices in which each vertex labelled by one of the 100! permutation.
Let us take a vertex whose labelling 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 × 1 = 109