Which of the following graphs has an Eulerian circuit? A. Any k-regular graph where k is an even number. B. A complete graph on 90 vertices. C. The complement of a cycle on 25 vertices. D. None of the above

GATE 2007 · Discrete Mathematics · Graph Connectivity · medium

Answer: The complement of a cycle on 25 vertices has an Eulerian circuit, which is option C.

1. Rule out options A and B: Option A: a k-regular graph with k even has all even degrees but can be disconnected (two disjoint even-regular graphs), so it is not guaranteed. Option B: K_90 has every vertex of degree 89, which is odd, so it has no Eulerian circuit.
2. Check option C: complement of C_25: In the cycle C_25 every vertex has degree 2, so in the complement every vertex has degree 24 - 2 = 22, which is even. The complement of a cycle on n >= 5 vertices is also connected.
3. Select the guaranteed graph: Only the complement of C_25 satisfies both conditions for certain, so it is the graph with an Eulerian circuit.