The following simple undirected graph is referred to as the Petersen graph.
[Petersen graph: 10 vertices, 15 edges, 3-regular, with an outer 5-cycle, an inner pentagram, and spokes connecting them.]
Which of the following statements is/are TRUE?
A. The chromatic number of the graph is 3.
B. The graph has a Hamiltonian path.
C. The following graph is isomorphic to the Petersen graph. [A different drawing of the Petersen graph is shown.]
D. The size of the largest independent set of the given graph is 3. (A subset of vertices of a graph form an independent set if no two vertices of the subset are adjacent.)
GATE 2022 · Discrete Mathematics · Graph Isomorphism · medium
Answer: A, B, C
Statement A — chromatic number 3: The Petersen graph contains odd cycles (girth 5), so chi >= 3. A valid 3-colouring exists. Hence chi = 3. Statement A is TRUE.
Statement B — Hamiltonian path: It is a known fact that the Petersen graph has a Hamiltonian path (e.g., 1-2-3-4-5-...) even though it has no Hamiltonian cycle. Statement B is TRUE.
Statements C and D: C: The alternate drawing shown is another standard representation of the Petersen graph (all such drawings are isomorphic due to its vertex-transitivity). Statement C is TRUE. D: The independence number alpha(Petersen) = 4, not 3. Statement D is FALSE.