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

Step 1: Recall the definitions. A graph is Eulerian if it has a closed trail that uses every edge exactly once (an Eulerian circuit). A graph is Hamiltonian if it has a cycle that visits every vertex exactly once. One condition is about edges, the other about vertices, so a graph can satisfy one without the other.

Step 2: Test option (A) with a counterexample. Consider the bowtie graph: two triangles sharing a single common vertex \(C\), with vertices \(A, B\) in the first triangle and \(D, E\) in the second. Every vertex except \(C\) has degree \(2\), and \(C\) has degree \(4\); all degrees are even and the graph is connected, so it has an Eulerian circuit. But no Hamiltonian cycle exists, because any cycle through \(C\) can use only two of its four edges, so one triangle would be left unvisited. This Eulerian graph is not Hamiltonian, so (A) is false.

Step 3: Test option (B) with a counterexample. Start with the 5-cycle \(1\text{-}2\text{-}3\text{-}4\text{-}5\text{-}1\), which is Hamiltonian. Add the chord \(1\text{-}3\). The cycle \(1\text{-}2\text{-}3\text{-}4\text{-}5\text{-}1\) still exists, so the graph remains Hamiltonian. But now vertices \(1\) and \(3\) have degree \(3\) (odd), so the graph has no Eulerian circuit. This Hamiltonian graph is not Eulerian, so (B) is false.

Step 4: Test option (C). By the handshaking lemma, the sum of all vertex degrees always equals twice the number of edges, so it is always even and can never be odd. The premise of (C) can never occur, so it cannot serve as a valid criterion for a graph being Hamiltonian, and (C) is false.

Step 5: Test option (D). This is Euler's classical theorem: a connected graph has an Eulerian circuit if and only if every vertex has even degree. This is a standard, always valid theorem, so (D) is true.

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