Let G be a graph with 100! vertices, with each vertex labelled by a distinct permutation of the numbers 1, 2, ..., 100. There is an edge between vertices u and v if and only if the label of v can be obtained by swapping two adjacent numbers in the label of u. Let d denote the degree of a vertex in G, and z denote the number of connected components of G. Then, g = 10 * z =

GATE 2018 · Algorithms · Strongly Connected Components · medium

Answer: z = 1 (the graph is connected), so g = 10 * z = 10.

1. Show the graph is connected (z = 1): Given any permutation p = (a_1, a_2, ..., a_100), we can perform bubble sort using only adjacent swaps to transform p into the identity permutation (1,2,...,100). Bubble sort uses only adjacent swaps. Therefore there is a path (sequence of edges) from any permutation p to the identity. Since any two permutations p and q both connect to the identity, they are connected to each other. Hence the entire graph G is one single connected component: z = 1.
2. Compute g = 10 * z: Since z = 1 (only one connected component), g = 10 * 1 = 10.