GATE CS 2018 Q.53 (CS Q.43): Graph Theory

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 =$ _____.

Your answer

Official answer and solution

Official answer: 109
From: Official GATE 2018 answer key

Solution

Determine vertex degree from adjacent transposition count, and connectivity from permutation generation properties.

In a permutation of length 100, there are $100 - 1 = 99$ adjacent positions: $(1,2), (2,3), \dots, (99,100)$ . Swapping any of these 99 adjacent pairs produces a distinct new permutation. Thus, every vertex has degree $y = 99$ .

Any permutation of $\{1, 2, \dots, 100\}$ can be generated from any other permutation using a finite sequence of adjacent transpositions (the foundation of algorithms such as bubble sort). Thus, the graph $G$ is fully connected, meaning the number of connected components is $z = 1$ .

Compute the required expression:

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

Final answer

109

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2018 Computer Science and Information Technology (CS)
Question: 53 of 65, printed as CS Q.43
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source