The following simple undirected graph is referred to as the Petersen graph. 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. 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: Statements A, B and C are true while D is false; the answer is A, B, C.

1. Statements A, B, C are true: A: the Petersen graph is non-bipartite (it has 5-cycles) yet 3-colourable, so its chromatic number is 3 - TRUE. B: it admits a path through all 10 vertices, so it has a Hamiltonian path - TRUE. C: the second drawing is another standard layout of the same 3-regular, girth-5 graph; it is isomorphic to the Petersen graph - TRUE.
2. Statement D is false: The largest independent set of the Petersen graph has 4 vertices (its independence number is 4), so the claim that the largest independent set has size 3 is too small - FALSE.