The GATE Grind

GATE 2022 CS – Question 50

Engineering Mathematics · Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) · 2 marks · Multiple select

The following simple undirected graph is referred to as the Peterson graph. [Figure: the standard Petersen graph on 10 vertices.]
Which of the following statements is/are TRUE?

Diagram for GATE 2022 CS question 50
  1. The chromatic number of the graph is 3.
  2. The graph has a Hamiltonian path.
  3. The following graph is isomorphic to the Peterson graph. [Figure: a 10-vertex drawing with a centre vertex.]
  4. 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.)

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 chromatic number 3 and has a Hamiltonian path (but no Hamiltonian cycle). Its maximum independent set has size 4, so D is false. The second drawing is not isomorphic to it.