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$.
More Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) questions
- GATE 2015 CS (CS1) Q44
- GATE 2017 CS (CS1) Q30
- GATE 2014 CS (CS1) Q61
- GATE 2014 CS (CS1) Q62
- GATE 2014 CS (CS2) Q13
- GATE 2014 CS (CS2) Q61
All Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) questions →