Which of the following graphs is isomorphic to the graph shown (a graph with 5 vertices each of degree 2, forming a 5-cycle C_5)? A. Graph A (vertices with degree not all 2) B. Graph B (5 vertices each of degree 2, a 5-cycle) C. Graph C (mixed degree sequence) D. Graph D (vertex with degree > 2)

GATE 2012 · Discrete Mathematics · Graph Isomorphism · medium

Answer: B. Graph B (5 vertices each of degree 2)

1. Extract invariants of the reference graph: Reference: 5 vertices, 5 edges, all vertex degrees = 2. Degree sequence: (2,2,2,2,2). The graph is C_5 with girth 5. A connected 2-regular graph on 5 vertices is uniquely C_5.
2. Match option B to the invariants: Option B (from the image on page 27): 5 vertices all of degree 2, 5 edges, connected. Degree sequence = (2,2,2,2,2). All invariants match the reference C_5. Options A, C, D have at least one vertex with degree != 2. Only option B is isomorphic to the reference graph.