Euler's theorem on circuits

Statement

Let \( G = (V, E) \) be a finite, connected multigraph (parallel edges and loops permitted, with the convention that a loop at \( v \) contributes \( 2 \) to \( \deg(v) \)) with at least one edge. Then \( G \) admits an Eulerian circuit — a closed walk \( v_0 e_1 v_1 e_2 \cdots e_m v_m = v_0 \) that traverses every edge of \( G \) exactly once — if and only if every vertex of \( G \) has even degree: \[ \exists \text{ Eulerian circuit in } G \iff \forall v \in V : \deg(v) \equiv 0 \pmod{2}. \]

Why it matters

This is the founding theorem of graph theory: Euler's 1736 resolution of the Königsberg bridge problem was the first time a question about a physical configuration was answered by abstracting it to vertices and edges and arguing about pure incidence structure. It is also the archetype of a good characterisation: a global, existential property (a single closed walk covering all edges) is decided by a purely local, trivially checkable condition (degree parity at each vertex).

Beyond its historical role, the theorem is the engine behind linear-time algorithms (Hierholzer), the polynomial solvability of the route-inspection ("Chinese postman") problem, the construction of de Bruijn sequences, and modern Eulerian-path methods in genome assembly. The stark contrast with the Hamiltonian circuit problem — identical-looking question about vertices instead of edges, yet NP-complete — makes it a standing lesson in how fragile algorithmic tractability is.

Hypotheses

Proof

Result

Corollaries & converses

• Eulerian trail (open) version. A finite connected graph has an open trail using every edge exactly once iff it has exactly two vertices of odd degree; the trail must run between them. (Join the two odd vertices by a new edge, apply the theorem, delete the new edge — Problem 3.)
• Veblen's theorem (one direction for free). If every vertex of \( G \) has even degree, then \( E(G) \) partitions into edge-disjoint cycles: cut the Eulerian circuit of each edge-bearing component at its repeated vertices (Problem — see Discussion).
• Handshake constraint. The number of odd-degree vertices in any finite graph is even (\( \sum_v \deg(v) = 2\lvert E \rvert \)); hence "exactly one odd vertex" can never occur, and pen-stroke puzzles have only the cases \( 0 \) or \( 2 \).
• Directed analogue. A digraph whose underlying graph is connected has a directed Eulerian circuit iff \( \deg^{+}(v) = \deg^{-}(v) \) for all \( v \); a consequence is that such a digraph is automatically strongly connected (Problem 5).
• Converse. The theorem is already a biconditional. But note the asymmetry of hypotheses: necessity (\( \exists \) circuit \( \Rightarrow \) all degrees even) holds without any connectivity assumption, whereas sufficiency genuinely needs connectivity — two disjoint triangles have all degrees even and no Eulerian circuit. So "all even \( \Rightarrow \) Eulerian" is false as a freestanding converse-style claim; the correct repair is: all degrees even iff each component is Eulerian or edgeless.

Fails without

Common errors

• Euler–Hamilton conflation. Concluding facts about visiting every vertex once (Hamiltonian) from a theorem about every edge once. \( K_4 \) is Hamiltonian but not Eulerian (all degrees \( 3 \)); the "bowtie" (two triangles sharing a vertex) is Eulerian but not Hamiltonian.
• Forgetting connectivity. Announcing "all degrees even, so Eulerian" for a graph never checked to be connected. Parity is local; the circuit is global.
• "No repeated vertices" misreading. An Eulerian circuit may revisit vertices freely — only edges are used once. Students often reject a correct circuit because a vertex appears twice (the bowtie's circuit must pass its centre twice).
• Parity of the sum instead of each vertex. Checking that \( \sum_v \deg(v) \) is even proves nothing: it is always even by the handshake lemma. Each individual degree must be even.
• Loop miscounting. Counting a loop as \( 1 \) toward its vertex's degree, which corrupts every parity check in multigraphs.
• Wrong digraph condition. Requiring "even total degree \( \deg^{+} + \deg^{-} \)" in a digraph. A vertex with \( \deg^{+} = 2, \deg^{-} = 0 \) has even total degree but no directed circuit can pass through it twice outward without ever entering; the correct condition is \( \deg^{+} = \deg^{-} \).
• Greedy overconfidence. Assuming any edge-greedy closed trail is automatically Eulerian. A maximal trail need not be maximum; the splice of Step 8 (or Fleury's don't-burn-bridges rule) is exactly what repairs a stuck trail.

Discussion

Euler presented his solution of the Königsberg bridge problem to the St Petersburg Academy in 1735, publishing it as Solutio problematis ad geometriam situs pertinentis (1736). The paper is routinely cited as the birth certificate of graph theory — and of topology, via Leibniz's phrase geometria situs, "the geometry of position": Euler saw that distances and shapes were irrelevant and only the incidence pattern mattered. Historical honesty requires a caveat: Euler carefully proved necessity and asserted sufficiency with only a sketch; the first complete published proof of sufficiency is Hierholzer's, appearing posthumously in 1873. The splice argument in Steps 4–8 above is essentially Hierholzer's, and run as an algorithm with appropriate data structures it constructs the circuit in \( \mathcal{O}(\lvert E \rvert) \) time.

The theorem is a paradigm of a good characterisation: membership ("Eulerian") and non-membership ("some odd vertex" or "disconnected") both come with short certificates. Contrast the Hamiltonian circuit problem, which asks the visually similar question for vertices and is NP-complete: no local condition can capture it unless P \( = \) NP. This single contrast — edges tractable, vertices intractable — recurs throughout combinatorial optimisation. It also explains why the route-inspection (Chinese postman) problem is polynomial: to traverse every edge of a connected graph at least once and return, one duplicates a minimum-weight set of paths pairing up the odd-degree vertices (a minimum-weight perfect matching on the odd vertices), thereby manufacturing the even-degree condition and then invoking this theorem.

Applications flow through the directed version. The de Bruijn digraph \( B(k, n) \) — vertices the words of length \( n - 1 \) over a \( k \)-letter alphabet, edges the words of length \( n \) — has \( \deg^{+} = \deg^{-} = k \) everywhere and is connected, so it carries a directed Eulerian circuit; reading off the circuit yields a de Bruijn sequence, a cyclic word of length \( k^{n} \) containing every length-\( n \) word exactly once. The BEST theorem (de Bruijn–van Aardenne-Ehrenfest–Smith–Tutte) goes further and counts Eulerian circuits in a digraph via arborescences and the matrix-tree theorem — whereas counting Eulerian circuits in undirected graphs is #P-complete. The same circle of ideas underlies Eulerian-path genome assemblers, which recover a DNA sequence as an Eulerian path in a k-mer de Bruijn graph rather than a Hamiltonian path in an overlap graph, precisely because the former is computable at scale.

Structurally, the even-degree condition says that \( E(G) \) is a member of the cycle space \( \mathcal{Z}(G) \subseteq \mathbb{F}_2^{E} \), the kernel of the incidence map \( \partial : \mathbb{F}_2^{E} \to \mathbb{F}_2^{V} \); Veblen's theorem identifies \( \mathcal{Z}(G) \) with the sets of edges expressible as disjoint unions of cycles, and Euler's theorem then reads: the full edge set is a sum of cycles that can be concatenated into one closed trail exactly when \( G \) is connected. For infinite graphs the naive statement fails (see "Fails without"), and the correct analogues are the Erdős–Grünwald–Vázsonyi theorems (1938) characterising one-way and two-way infinite Eulerian trails in countable graphs — conditions involving finitely many odd vertices and the behaviour of ends. Common misconceptions. "One pen stroke" puzzles are about open trails, not circuits: the house-of-Santa-Claus figure is drawable in one stroke (exactly two odd vertices) but you cannot end where you began. And even-degree everywhere does not make a graph Eulerian without connectivity — it makes each edge-bearing component Eulerian separately.

Worked examples

Example 1 (Königsberg, 1736). The city had four land masses — north bank \( B \), south bank \( C \), island \( A \) (Kneiphof), east bank \( D \) — joined by seven bridges: \( A \)–\( B \) twice, \( A \)–\( C \) twice, and one bridge each for \( A \)–\( D \), \( B \)–\( D \), \( C \)–\( D \). Can a stroll cross every bridge exactly once and return home?

Example 2 (\( K_5 \): existence and explicit construction by Hierholzer splicing). Let \( K_5 \) have vertices \( \{1, 2, 3, 4, 5\} \) and all \( \binom{5}{2} = 10 \) edges. Decide whether an Eulerian circuit exists and construct one.

Problems

1. Does the complete bipartite graph \( K_{2,4} \) have an Eulerian circuit? If so, exhibit one; if not, prove it.
   Solution

   Let the parts be \( \{a, b\} \) and \( \{1, 2, 3, 4\} \). Every vertex in the first part has degree \( 4 \); every vertex in the second part has degree \( 2 \). All degrees are even, and \( K_{2,4} \) is connected (any two vertices are joined via a vertex of the opposite part). By Euler's theorem an Eulerian circuit exists. Explicitly: \[ a \to 1 \to b \to 2 \to a \to 3 \to b \to 4 \to a, \] which uses the edges \( a1, 1b, b2, 2a, a3, 3b, b4, 4a \) — eight distinct edges, and \( \lvert E(K_{2,4}) \rvert = 2 \cdot 4 = 8 \), so every edge is used exactly once and the walk is closed. It is an Eulerian circuit.

2. For which \( n \geq 2 \) does \( K_n \) have an Eulerian circuit? For which \( m, n \geq 1 \) does \( K_{m,n} \)?
   Solution

   \( K_n \): it is connected, and every vertex has degree \( n - 1 \). By Euler's theorem, \( K_n \) is Eulerian iff \( n - 1 \) is even, i.e. iff \( n \) is odd. So the answer is: all odd \( n \geq 3 \) (e.g. \( K_3, K_5, K_7, \ldots \)), and no even \( n \) — for even \( n \) every vertex is odd, so by necessity there is no circuit (indeed for even \( n \geq 4 \) there are at least four odd vertices, so not even an open Eulerian trail).

   \( K_{m,n} \): it is connected for \( m, n \geq 1 \). Vertices in the \( m \)-side have degree \( n \); vertices in the \( n \)-side have degree \( m \). By Euler's theorem, \( K_{m,n} \) is Eulerian iff both \( m \) and \( n \) are even (and positive, so that edges exist). E.g. \( K_{2,2} \) (the \( 4 \)-cycle) and \( K_{2,4} \) are Eulerian; \( K_{2,3} \) and \( K_{3,3} \) are not.

3. Prove the open-trail corollary: a finite connected graph \( G \) has an Eulerian trail (an open walk traversing every edge exactly once) if and only if it has exactly two vertices of odd degree; and any such trail runs between the two odd vertices.
   Solution

   (\( \Leftarrow \)) Suppose exactly two vertices \( x \neq y \) have odd degree. Form the multigraph \( G^{+} = G + e^{*} \), where \( e^{*} \) is a new edge joining \( x \) and \( y \) (allowed even if \( x, y \) are already adjacent, since we work with multigraphs). In \( G^{+} \), the degrees of \( x \) and \( y \) increase by \( 1 \) and become even, and all other degrees are unchanged and even; \( G^{+} \) is connected because \( G \) is. By Euler's theorem, \( G^{+} \) has an Eulerian circuit \( C \). Since a circuit is a cyclic object, re-root \( C \) so that \( e^{*} \) is its first edge: \( C = x \, e^{*} \, y \cdots x \). Deleting the initial \( e^{*} \) leaves a trail from \( y \) to \( x \) that uses every edge of \( G \) exactly once — an Eulerian trail between the odd vertices.

   (\( \Rightarrow \)) Suppose \( G \) has an Eulerian trail \( W \) from \( x \) to \( y \), \( x \neq y \). The edge-end count of Steps 1–2 of the main proof shows: at every vertex \( v \notin \{x, y\} \) the trail uses edge-ends in pairs, so \( \deg(v) \) is even; at \( x \) the initial departure is unpaired, so \( \deg(x) \) is odd, and symmetrically \( \deg(y) \) is odd. Hence exactly two vertices are odd. (If \( x = y \), the trail is a circuit and all degrees are even — the case of the main theorem, with zero odd vertices.) The handshake lemma confirms consistency: the number of odd vertices is always even, so "exactly one odd vertex" can never arise.

4. A standard "double-six" domino set consists of all \( 28 \) tiles \( [i \mid j] \) with \( 0 \leq i \leq j \leq 6 \). Tiles may be laid end to end when the touching halves show the same number. Prove that the entire set can be arranged in a single closed ring.
   Solution

   Build a multigraph \( G \) with \( V = \{0, 1, \ldots, 6\} \) and one edge per tile: the tile \( [i \mid j] \) with \( i \neq j \) is an edge joining \( i \) and \( j \), and the double \( [i \mid i] \) is a loop at \( i \). A closed ring of all \( 28 \) tiles, matched end to end, is exactly an Eulerian circuit of \( G \): traversing the edge \( [i \mid j] \) corresponds to laying that tile with the \( i \)-end adjoining the previous tile and the \( j \)-end adjoining the next.

   Degrees: each vertex \( i \) is joined to each of the \( 6 \) other vertices by one edge, contributing \( 6 \), and carries one loop, contributing \( 2 \) (loop convention). So \( \deg(i) = 8 \) for every \( i \): all even. \( G \) is connected (it contains \( K_7 \)). By Euler's theorem, an Eulerian circuit exists, and reading off its edges in order gives the closed domino ring. \( \square \)

   Remark. Without the doubles, the \( 21 \) remaining tiles form \( K_7 \), with all degrees \( 6 \) — still even, so a closed ring of the non-doubles also exists; each double \( [i \mid i] \) can then be inserted at any passage through \( i \). By contrast, the analogous "double-seven" set on \( \{0, \ldots, 7\} \) fails: without doubles the underlying graph is \( K_8 \) with all degrees \( 7 \) odd, and doubles only add \( 2 \), so all eight vertices stay odd and no closed ring of the full set exists.

5. (Directed version.) Let \( D \) be a finite digraph with at least one arc whose underlying graph is connected, and suppose \( \deg^{+}(v) = \deg^{-}(v) \) for every vertex \( v \). Prove that \( D \) has a directed Eulerian circuit, and deduce that \( D \) is strongly connected.
   Solution

   Directed Exit Lemma. If every vertex of a finite digraph \( H \) satisfies \( \deg_H^{+}(v) = \deg_H^{-}(v) \) and \( \deg_H^{+}(u) \gt 0 \), then \( H \) contains a directed closed trail of positive length through \( u \). Proof: extend a directed trail from \( u \), never reusing an arc. If the trail currently ends at \( w \neq u \), then so far it has entered \( w \) one more time than it has left (each earlier passage pairs one entry with one exit; the final arrival is an unmatched entry). Hence used-out \( \lt \) used-in \( \leq \deg_H^{-}(w) = \deg_H^{+}(w) \), so an unused out-arc at \( w \) exists and the trail extends. Finiteness forces termination, which can only occur at \( u \). \( \square \)

   Main argument. Mirror Steps 4–9 of the undirected proof. Choose a directed closed trail \( T \) with the maximum number of arcs (nonempty by the Lemma, since some vertex has \( \deg^{+} \gt 0 \)). If \( T \) misses some arc, let \( H = D - A(T) \). Removing a closed trail removes equally many in-arcs as out-arcs at every vertex (each passage through a vertex uses one of each; the start/end occurrence likewise pairs the first departure with the last arrival), so \( H \) still satisfies \( \deg_H^{+} = \deg_H^{-} \) everywhere. Connectivity of the underlying graph gives, exactly as in Step 6, a vertex \( w \) on \( T \) incident (in either direction) with an arc of \( H \); since at every vertex of \( H \) in-degree equals out-degree, \( \deg_H^{+}(w) \gt 0 \) whenever \( w \) meets any \( H \)-arc (an arc into \( w \) forces \( \deg_H^{-}(w) \gt 0 \), hence \( \deg_H^{+}(w) = \deg_H^{-}(w) \gt 0 \)). The Directed Exit Lemma yields a closed trail \( T' \) in \( H \) through \( w \); splicing \( T' \) into \( T \) at \( w \) produces a strictly longer directed closed trail, contradicting maximality. Hence \( T \) uses every arc: a directed Eulerian circuit.

   Strong connectivity. Every arc lies on the circuit \( T \). First note every vertex lies on \( T \): a vertex \( v \) off \( T \) would have \( \deg^{+}(v) = \deg^{-}(v) = 0 \) (all arcs are on \( T \)), and then \( v \) is isolated in the underlying graph, contradicting its connectivity (as \( D \) has at least one arc, so at least one other vertex). Now for any ordered pair \( (v_1, v_2) \) of vertices on \( T \), follow \( T \) forward from an occurrence of \( v_1 \); since \( T \) is closed and passes through \( v_2 \), a directed \( v_1 \)–\( v_2 \) walk exists. Hence \( D \) is strongly connected. \( \square \)