GATE 2022 CS Q.50: solution and answer

GATE 2022 · CSQ.50 · 2 marks · MSQ

The following simple undirected graph is referred to as the Peterson graph. Which of the following statements is/are TRUE?

GATE 2022 CS question 50: Top figure: the Peterson graph drawn as an outer regular pentagon with 5 vertices and an inner pentagram (five-pointed… — Figure from the GATE 2022 CS paper. It is part of the question.

(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. [Figure — a 9-cycle of boundary vertices plus a centre vertex, with six chords as described]
(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.)

Answer and solution

ANSWER

A, B and C are true; D is false.

Official answer: A, B, CSource: Official answer key, GATE 2022 CS (IIT Kharagpur)

Label the Peterson graph: outer 5-cycle $o_{0}, \dots, o_{4}$ , spokes $o_{k} - i_{k}$ , inner edges $i_{k} - i_{k \pm 2}$ (indices mod 5). It is 3-regular with 10 vertices and 15 edges, and it has girth 5.
(A) The outer 5-cycle is an odd cycle, so $χ \geq 3$ . A 3-colouring: $o_{0}, \dots, o_{4} = 1, 2, 1, 2, 3$ and $i_{0}, \dots, i_{4} = 2, 3, 3, 1, 1$ . Outer edges: $1 - 2, 2 - 1, 1 - 2, 2 - 3, 3 - 1$ all differ. Spokes: $(1, 2), (2, 3), (1, 3), (2, 1), (3, 1)$ all differ. Inner edges $i_{0} i_{2}, i_{1} i_{3}, i_{2} i_{4}, i_{3} i_{0}, i_{4} i_{1}$ have colours $(2, 3), (3, 1), (3, 1), (1, 2), (1, 3)$ , all differ. So $χ = 3$ . TRUE.
(B) Hamiltonian path: $o_{0}, o_{1}, o_{2}, o_{3}, o_{4}, i_{4}, i_{1}, i_{3}, i_{0}, i_{2}$ . The consecutive pairs are edges ( $o_{4} i_{4}$ is a spoke; $i_{4} i_{1}, i_{1} i_{3}, i_{3} i_{0}, i_{0} i_{2}$ are inner edges) and all 10 vertices appear once. TRUE. (The Peterson graph has no Hamiltonian cycle, but a path exists.)
(C) A simple cubic graph on 10 vertices with girth 5 is unique: the Peterson graph. In the figure, number the 9-cycle $0, \dots, 8$ clockwise from the top (1 = upper-right, 2 = right, 3 = lower-right, 4 = bottom-right, 5 = bottom-left, 6 = lower-left, 7 = left, 8 = upper-left) and call the centre $c$ . The chords are $0 c, 3 c, 6 c, 2 - 7, 4 - 8, 1 - 5$ , so every vertex has degree 3 (15 edges).
Girth check: the centre's neighbours $0, 3, 6$ are pairwise non-adjacent and have no common neighbour other than $c$ (neighbours of $0$ : $1, 8$ ; of $3$ : $2, 4$ ; of $6$ : $5, 7$ ), so no triangle or 4-cycle passes through $c$ . Each chord spans 4 cycle edges, so a single chord gives only 5-cycles. A 4-cycle using two chords would need their ends joined by cycle edges: for $2 - 7$ and $4 - 8$ , $7 \sim 8$ but $2 \neq \sim 4$ ; for $2 - 7$ and $1 - 5$ , $2 \sim 1$ but $7 \neq \sim 5$ ; for $4 - 8$ and $1 - 5$ , $4 \sim 5$ but $8 \neq \sim 1$ . So there is no 3- or 4-cycle, the girth is 5, and the graph is isomorphic to the Peterson graph. TRUE.
(D) Each of the two 5-cycles allows at most $⌊ 5/2 ⌋ = 2$ independent vertices, so $α \leq 4$ . The set ${o_{0}, o_{2}, i_{3}, i_{4}}$ is independent: $o_{0}$ is adjacent only to $o_{1}, o_{4}, i_{0}$ ; $o_{2}$ only to $o_{1}, o_{3}, i_{2}$ ; $i_{3}$ only to $i_{0}, i_{1}, o_{3}$ ; $i_{4}$ only to $i_{1}, i_{2}, o_{4}$ . So $α = 4 \neq = 3$ . FALSE.
Hence the true statements are A, B and C.

KEY IDEA

The Peterson graph is the unique 3-regular graph on 10 vertices with girth 5, so another cubic 10-vertex graph with no triangle or 4-cycle is isomorphic to it. Its chromatic number is 3, it has a Hamiltonian path but no Hamiltonian cycle, and its largest independent set has size 4.

WATCH OUT FOR

Judging the isomorphism in (C) by how the drawing looks instead of checking degrees and girth. Another slip is assuming that because the Peterson graph has no Hamiltonian cycle it has no Hamiltonian path, or taking the independence number to be 3 instead of 4.

From the GATE 2022 CS paper. Every question of this paper · Download the full paper · All 14 Graph theory questions, with notes

GATE 2022 CS Q.50: solution and answer

Answer and solution

More Graph theory questions