GATE CSE 2018 | Question: 43

Question

Let $G$ be a graph with $100!$ vertices, with each vertex labelled by a distinct permutation of the numbers $1, 2,\ldots, 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=$ ______.

Comments

Yes but the degree of the vertex changes.

---

Then they would’ve mentioned in-degree and out-degree separately , wouldn’t they ? By mentioning degree only , it also hints towards undirected graph.

---

For geting z connected component try to take 1,2,3 and gnrate all 6 combinations of it 

and then try start with (1,2,3) and try to get one of node among those 6 nodes by swaping any two adjacent labels and so on ……..

at the end you find that every vertex or label is reachable from every label so that z=1

Answer 1

Here its mentioned that edge id obtained only when”swapping two adjacent numbers”.  Hence degree of each vertex will be 99 and the graph is undirected and connected hence itself is a component. thus y=99 and z=1, so value becomes 109