GATE 2022 CS – Question 50
The following simple undirected graph is referred to as the Peterson graph.
Which of the following statements is/are TRUE?

Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (A) The chromatic number of the graph is 3.; (B) The graph has a Hamiltonian path.
Explanation
The Petersen graph has 10 vertices, is 3-regular, has girth 5 and is non-Hamiltonian (no Hamiltonian cycle) but has a Hamiltonian path.
- **(A) True.** It contains odd cycles (5-cycles), so it needs at least 3 colours, and a proper 3-colouring exists. $\chi=3$.
- **(B) True.** It has a Hamiltonian path.
- **(D) False.** Its maximum independent set has size **4**, not 3.
- **(C)** The second drawing is not isomorphic to the Petersen graph (it does not have the Petersen graph's structure), so (C) is false.
Answer: A, B.
More Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) questions
- GATE 2022 CS Q52
- GATE 2022 CS Q58
- GATE 2021 CS (CS1) Q26
- GATE 2020 CS Q62
- GATE 2019 CS Q22
- GATE 2019 CS Q56
All Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) questions →