GATE CS 1997 Q6.2 — Graphs

Two vertices $i$ and $j$ are adjacent if and only if $|i - j| = 8$ or $|i - j| = 12$.

If there exists a path between two vertices $i$ and $j$, then their difference must be a linear combination of the step sizes $8$ and $12$:

By Bézout's identity, the set of all such linear combinations is precisely the set of multiples of the greatest common divisor:

This implies that $i$ and $j$ can belong to the same connected component only if $i \equiv j \pmod 4$. This partitions the $100$ vertices into $4$ equivalence classes modulo $4$:

• $C_1 = \{1, 5, 9, \dots, 97\}$
• $C_2 = \{2, 6, 10, \dots, 98\}$
• $C_3 = \{3, 7, 11, \dots, 99\}$
• $C_4 = \{4, 8, 12, \dots, 100\}$

Since we can transition by $+4$ using the sequence of steps $+12$ followed by $-8$ (and vice versa) without exceeding the boundaries $[1, 100]$, each of these $4$ equivalence classes is fully connected. Thus, there are exactly $4$ connected components.