Exercise 1685Combinatorics › Graph theoryL1Added 3 Nov 2026

Eulerian circuits

#Eulerian#Euler circuit#degree

Statement

Show that a connected graph has an Eulerian circuit (closed walk using every edge exactly once) iff every vertex has even degree.

Hint

$(\Rightarrow)$ : each time the circuit enters a vertex, it leaves. $(\Leftarrow)$ : build a circuit greedily and splice.

Show solutionHide solution

Solution

$(\Rightarrow)$ . In an Eulerian circuit, each visit to a vertex contributes $2$ to its degree (one entering edge, one leaving). So all degrees are even.

$(\Leftarrow)$ . Suppose all degrees even. Pick any vertex, extend a path greedily until it returns (possible since each interior vertex has even degree). Remove the cycle; the remaining edges form components with all even degrees. Apply induction and splice.

Conclusion. Eulerian circuit exists iff all degrees even and the graph is connected.

Eulerian circuits

Statement

Solution

More problems in Graph theory