GATE CS 2022 Q.50: Graph Theory

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

The Petersen graph drawn with an outer 5-cycle, an inner 5-pointed star, and 5 radial spokes connecting outer vertices to inner vertices.

Which of the following statements is/are TRUE?

The chromatic number of the graph is 3.

The graph has a Hamiltonian path.

The following graph is isomorphic to the Peterson graph.

A 3-regular 10-vertex graph drawn as an outer 9-cycle with one central vertex connected to three outer vertices spaced 3 steps apart, and three chords connecting the remaining pairs at distance 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.)

Official answer and solution

Official answer: A, B and C
From: Official GATE 2022 answer key

Solution

Evaluate graph-theoretic properties of the Petersen graph including chromatic number, Hamiltonian paths, and independence number.

The Petersen graph is a 3-regular graph with 10 vertices and 15 edges:

(A) TRUE: The Petersen graph contains odd cycles of length 5, so it is not bipartite and its chromatic number $\chi(G) \ge 3$ . A valid 3-coloring can be constructed (e.g., coloring outer cycle with colors 1, 2, 1, 2, 3 and inner vertices appropriately). Hence $\chi(G) = 3$ .
(B) TRUE: Although the Petersen graph has no Hamiltonian cycle (it is non-Hamiltonian), it contains a Hamiltonian path. For example, numbering outer vertices $0, 1, 2, 3, 4$ and corresponding inner vertices $5, 6, 7, 8, 9$ , the path $0 - 1 - 2 - 3 - 4 - 9 - 7 - 5 - 8 - 6$ visits all 10 vertices.
(C) TRUE: The graph shown in Option (C) is a standard alternative 3-regular drawing of the Petersen graph with 10 vertices, girth 5, and identical adjacency relationships, making it isomorphic to the Petersen graph.
(D) FALSE: The maximum independent set of the Petersen graph has size $\alpha(G) = 4$ (for example, take two non-adjacent outer vertices and two non-adjacent inner vertices that do not share edges with them). Thus the maximum independent set is 4, not 3.

Therefore, (A), (B), and (C) are TRUE.

Final answer

Options (A), (B), (C)

Common trap

Confusing a Hamiltonian path (visits all vertices) with a Hamiltonian cycle (must return to the starting vertex).

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2022 Computer Science and Information Technology (CS)
Question: 50 of 65
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source