Skip to content
GATEiit

GATE CSE 2022 Q50: Properties of the Petersen graph

Question

The following simple undirected graph is referred to as the Peterson graph (left in the figure).

Which of the following statements is/are TRUE?

Left: the Petersen graph drawn as an outer pentagon joined to an inner pentagram. Right: the graph of option (C), a 9-cycle with a centre vertex joined to three of its vertices and chords across the cycle
Tap the figure to enlarge

Try it: multiple select: one or more correct options

Select one or more options
Select all correct options. No negative marking, no partial marks.
Show answer and explanation

Answer: A, B, C (official GATE 2022 final answer key)

Concept used: The Petersen graph is 3-regular on 10 vertices, has girth 5, is 3-colourable, has a Hamiltonian path (but no Hamiltonian cycle), and has independence number 4.

First step: Try 3-colouring the outer pentagon (needs 3 colours, odd cycle) and extend to the star; then look for 4 mutually non-adjacent vertices.

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

WhatsAppDownload image

Source: official GATE 2022 CS question paper and final answer key, organised by IIT Kharagpur. Question paper · Answer key

More Engineering Mathematics PYQs

PracticePractise Engineering Mathematics questions →Full paperAll GATE CSE 2022 questions →