GATE 2018 CS Q.43: solution and answer

GATE 2018 · CSQ.43 · 2 marks · NAT

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 + 10 z =$ ______.

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

$y + 10 z = 109$

Official answer: 109Source: Official answer key, GATE 2018 CS (IIT Guwahati)

Each vertex is a permutation of $1, 2, \dots, 100$ . Two vertices are joined exactly when one label comes from the other by swapping two adjacent numbers (two neighbouring positions).
Degree: a label has $99$ pairs of neighbouring positions $(i, i + 1)$ , for $i = 1, \dots, 99$ . Swapping the entries in positions $i$ and $i + 1$ always gives a different permutation, because the two numbers are distinct. Two different position pairs give different results, because they change different positions. So each vertex has exactly $99$ neighbours, and $y = 99$ .
Components: any permutation can be sorted into $1, 2, \dots, 100$ by repeatedly swapping an adjacent out-of-order pair (bubble sort). Each such swap moves along an edge, and edges are undirected. So every vertex is joined by a path to the identity permutation.
Every vertex lies in the same component as the identity permutation, so $G$ is connected and $z = 1$ .
Therefore $y + 10 z = 99 + 10 \times 1 = 109$ .

KEY IDEA

The graph has one vertex per permutation of 100 numbers and joins two permutations that differ by one adjacent swap. Each vertex has one neighbour per neighbouring position pair, which gives 99. Adjacent swaps can sort any permutation (bubble sort), so the graph is connected.

WATCH OUT FOR

Using $100$ or $(2 100)$ as the degree. Only swaps of neighbouring positions count, so the degree is $99$ , not the number of all pairs of positions. Another slip is to think the graph splits by parity of permutation. An adjacent swap changes parity, so the edges join even and odd permutations, but the graph is still connected.

From the GATE 2018 CS paper. Every question of this paper · Download the full paper · All 14 Graph theory questions, with notes

GATE 2018 CS Q.43: solution and answer

Answer and solution

More Graph theory questions