GATE CS 2022 Q40 — Graphs: Connectivity, Matching, Colouring

Let us analyze each option for the Petersen graph $G$:

• Option A (True): The Petersen graph contains odd cycles (5-cycles), so its chromatic number $\chi(G) \ge 3$. Since it is a $3$-regular connected graph that is neither a complete graph nor an odd cycle, by Brooks' Theorem, $\chi(G) \le 3$. Thus, $\chi(G) = 3$.
• Option B (True): Although the Petersen graph is famously non-Hamiltonian (it has no Hamiltonian cycle), it does possess a Hamiltonian path. For example, labeling the outer cycle $u_0, u_1, u_2, u_3, u_4$ and the inner star $v_0, v_1, v_2, v_3, v_4$ (with $u_i$ adjacent to $v_i$), one Hamiltonian path is: $$u_0 \to u_1 \to u_2 \to u_3 \to u_4 \to v_4 \to v_1 \to v_3 \to v_0 \to v_2$$
• Option C (True): The second graph is a well-known isomorphic drawing of the Petersen graph. It consists of a 9-cycle with a central vertex connected to three symmetric vertices on the cycle (at distance 3 from each other). Both graphs have 10 vertices, 15 edges, are 3-regular, and share the same structural properties.
• Option D (False): The size of the largest independent set (independence number $\alpha(G)$) of the Petersen graph is $4$, not $3$. For example, the set of vertices $\{u_0, u_2, v_1, v_3\}$ is independent because no two of these vertices share an edge.