The following simple undirected graph is referred to as the Petersen graph.…
2022
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.)
Attempted by 79 students.
Show answer & explanation
Correct answer: A, B, C
The true statements are 1, 2, and 3.
1. The chromatic number is 3. The Petersen graph contains a 5-cycle, so it is not bipartite and needs at least 3 colors. A valid 3-coloring exists, so the chromatic number is exactly 3.
2. The graph has a Hamiltonian path. The Petersen graph is non-Hamiltonian, meaning it has no Hamiltonian cycle, but it is traceable: a Hamiltonian path visiting all 10 vertices exists. Equivalently, deleting any vertex gives a Hamiltonian cycle in the remaining graph, and the deleted vertex can be attached at one end to obtain a Hamiltonian path.
3. The second drawing is isomorphic to the Petersen graph. It is a redrawing with the same adjacency structure; crossings and geometric placement do not affect graph isomorphism.
4. The largest independent set is not of size 3. The independence number of the Petersen graph is 4, so this statement is false.
Therefore, statements 1, 2, and 3 are true, while statement 4 is false.