The following simple undirected graph is referred to as the Peterson graph.…

GATE · 2022 · CS · Computer Science & IT

The following simple undirected graph is referred to as the Peterson graph.

Which of the following statements is/are TRUE?

1. A.

   The chromatic number of the graph is 3.

2. B.

   The graph has a Hamiltonian path.

3. C.

   The following graph is isomorphic to the Peterson graph.

   

4. 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 128 students.