Question

Which of the following is a necessary condition for a connected graph to have an Eulerian circuit?

• A. The graph has at most two vertices of odd degree
• B. The graph is complete
• C. The graph contains a Hamiltonian path
• D. All vertices have even degree

Hint:

Every entry into a vertex needs an exit. Count the parity of degrees at each vertex.

Answer 1

The Correct Option is D

Step 1: An Eulerian circuit is a closed walk that uses every edge exactly once and returns to the start.

Step 2: Euler's theorem says a connected graph has an Eulerian circuit if and only if every vertex has even degree. Each time the walk enters a vertex it must also leave, so edges pair up at every vertex.

Step 3: Check the options. At most two odd vertices is the condition for an Eulerian path, not a circuit. Completeness and a Hamiltonian path are unrelated. Only option (D), all vertices have even degree, is the required condition.