GATE CS 2007 Q23 — Graphs: Connectivity, Matching, Colouring

An undirected graph has an Eulerian circuit if and only if it is connected (ignoring isolated vertices) and every vertex has an even degree.

• Option A: A $k$-regular graph with even $k$ does not have to be connected. For example, a graph consisting of two disjoint triangles ($C_3 \cup C_3$) is $2$-regular but disconnected, so it has no Eulerian circuit.
• Option B: In a complete graph $K_{90}$, each vertex has degree $90 - 1 = 89$, which is odd. Thus, it cannot have an Eulerian circuit.
• Option C: Let $G$ be a cycle on $25$ vertices ($C_{25}$). In $G$, every vertex has degree $2$. In its complement $\overline{G}$, the degree of each vertex is: $$\text{deg}_{\overline{G}}(v) = (n - 1) - \text{deg}_{G}(v) = (25 - 1) - 2 = 22$$ Since $22$ is even, all vertices in $\overline{G}$ have an even degree. Additionally, the complement of any cycle of length $n \ge 5$ is connected. Since $\overline{G}$ is connected and all vertices have even degrees, it contains an Eulerian circuit.