GATE 2018 CS – Question 53
Let $G$ be a graph with $100!$ vertices, with each vertex labelled by a distinct permutation of the numbers $1,2,\dots,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=$ ________.
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 109
Explanation
Each permutation has 99 adjacent pairs, so every vertex has degree $y=99$. Adjacent swaps generate all permutations, so the graph is connected, $z=1$. Thus $y+10z=99+10=109$.