GATE CS 2018 Q43 — Graph Traversals (BFS, DFS)

To find the value of $y + 10z$, we need to determine the degree of a vertex ($y$) and the number of connected components ($z$) in the graph $G$.

1. Finding the Degree of a Vertex ($y$)

Each vertex in $G$ represents a unique permutation of the numbers $1, 2, \ldots, 100$.

• An edge exists between two vertices if one permutation can be obtained from the other by swapping exactly two adjacent elements.
• For any permutation of length $n = 100$, there are exactly $n - 1 = 99$ adjacent pairs that can be swapped: $(1, 2), (2, 3), \ldots, (99, 100)$.
• Swapping any of these adjacent pairs produces a unique, valid permutation.

Since the graph is undirected, the degree of every vertex is the same:

2. Finding the Number of Connected Components ($z$)

A fundamental property of permutations is that any permutation can be transformed into any other permutation of the same set using a sequence of adjacent swaps (transpositions). This is the underlying principle of sorting algorithms like Bubble Sort.

• Since we can transition from any vertex (permutation) to any other vertex via a sequence of adjacent swaps, there is a path between every pair of vertices in $G$.
• This means the graph $G$ is fully connected.

Thus, the number of connected components is:

3. Calculating $y + 10z$

Substituting the values of $y$ and $z$: