Let G be a graph with 100! vertices, with each vertex labelled by a distinct permutation of the numbers 1,2, … , 100

Q. 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 𝑢 and 𝑣 if and only if the label of 𝑢 can be obtained by swapping two adjacent numbers in the label of 𝑣. Let 𝑦 denote the degree of a vertex in G, and 𝑧 denote the number of connected components in G. Then, 𝑦 + 10𝑧 =          

.Ans: 109

Sol:

There is an edge between vertices u and v if the label of u can be obtained by swapping two adjacent numbers in the label of v. 
Then the set of swapping numbers will be {(1, 2), (2, 3), ………..(9, 9)} 
There will be 99 such sets, i.e. number of edges = 99 
and each vertex will have 99 edges corresponding to it.  

Say graph with 3! vertices, then vertices will be like {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}… Let\’s pick vertex {123}, degree will be 2 since it will be connected with two other vertices {213} and {132}.

We can conclude that for n, degree will be n-1.

SO, degree of each vertex = 99 (as said y) 
As the vertices are connected together, the number of connected components formed will be 1 (as said z).

y+10z = 99+10(1) = 109