Question

Which one of the following options is always true?

• A. Every Eulerian graph is also Hamiltonian.
• B. Every Hamiltonian graph is also Eulerian.
• C. If the sum of degrees of vertices is odd, the graph is Hamiltonian.
• D. If all vertices have even degree, the graph has an Eulerian circuit.

Hint:

Recall Euler's theorem: a connected graph has an Eulerian circuit exactly when every vertex has even degree.

Answer 1

The Correct Option is D

Method: Compare the two families of graphs side by side, then justify option (D) from the constructive idea behind Euler's proof rather than a counterexample search.

Eulerian and Hamiltonian are independent properties. A graph can fall into four cases: both Eulerian and Hamiltonian (a single cycle $C_n$, which uses every edge once and every vertex once), Eulerian but not Hamiltonian (the bowtie graph, where a cut vertex blocks any Hamiltonian cycle), Hamiltonian but not Eulerian (a cycle with one extra chord, which keeps the Hamiltonian cycle but creates odd-degree vertices), or neither. Since all four cases occur, neither "Eulerian implies Hamiltonian" (option A) nor "Hamiltonian implies Eulerian" (option B) can be a universal law.

For option (C), the handshaking lemma states $\sum_v \deg(v) = 2|E|$, which is always an even number since it is twice an integer. The condition "sum of degrees is odd" describes a situation that never happens for any graph, so it is not a usable characterization of Hamiltonian graphs.

For option (D), recall the idea behind Euler's theorem: if every vertex of a connected graph has even degree, start a trail at any vertex and keep walking along unused edges. Because every vertex has even degree, whenever the trail enters a vertex it can always leave again through an unused edge, except possibly at the start. This forces the trail to close up into a circuit at the starting vertex. If the circuit does not yet cover all edges, splice in another such circuit found on the remaining edges (which also has all even degrees), repeating until every edge is included. This construction always succeeds precisely when all degrees are even, which is why (D) holds in general.

\[\boxed{\text{Option (D)}}\]