Question

The following simple undirected graph is referred to as the Peterson 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 Peterson graph.
  
• D. The size of the largest independent set of the given graph is 3.

Hint:

The Peterson graph is a famous example in graph theory, characterized by its chromatic number of 3, Hamiltonian path, and Hamiltonian cycle. It is also used to demonstrate concepts like graph isomorphism and independent sets.

Answer 1

The Correct Option is A, B, C

Let's evaluate each statement:
Statement (A): The chromatic number of the graph is 3.
This statement is true. The chromatic number of a graph is the minimum number of colors required to color the vertices such that no two adjacent vertices share the same color. For the Peterson graph, it is well-known that the chromatic number is 3. This is because the Peterson graph is a 3-regular graph, and the chromatic number of a 3-regular graph on 10 vertices is 3.
Statement (B): The graph has a Hamiltonian path.
This statement is true. The Peterson graph has a Hamiltonian cycle (a cycle that visits each vertex exactly once), and as a result, it also has a Hamiltonian path (a path that visits each vertex exactly once). The existence of a Hamiltonian cycle implies the existence of a Hamiltonian path.
Statement (C): The following graph is isomorphic to the Peterson graph.
This statement is true. The second graph shown in the question is indeed isomorphic to the Peterson graph. Two graphs are isomorphic if there is a one-to-one correspondence between their vertices and edges, such that the adjacency relations are preserved. The second graph has the same structure and properties as the Peterson graph, meaning it is isomorphic to it.
Statement (D): The size of the largest independent set of the given graph is 3.
This statement is false. The size of the largest independent set (a set of vertices where no two vertices are adjacent) in the Peterson graph is 4, not 3. In the Peterson graph, the largest independent set consists of 4 vertices, not 3. Hence, Statement (D) is incorrect.
Thus, the correct answers are (A), (B), and (C).