Proving the Undirected Euler Circuit Characterization

The Circuit Characterization

An Euler circuit is a closed route that uses every edge exactly once. Its vertices may repeat: what must not repeat is an edge. The characterization proved here gives a precise test for when such a route exists in a connected undirected graph. The constructive direction uses a simple idea: build a closed trail, then splice in further closed trails until no edge remains unused.

Throughout, graphs are finite and simple. A trail is a walk with no repeated edges; vertices may repeat. A closed trail starts and ends at the same vertex. An Euler circuit is a closed trail that uses every edge of the graph exactly once. A graph is connected if every pair of its vertices can be joined by a path.

Both conditions matter. The degree condition is necessary because a circuit pairs each arrival at a vertex with a departure. For sufficiency, even degrees let us keep extending a trail until it closes; connectedness then ensures that any edges left unused can be reached from the circuit already built.

Why an Euler Circuit Forces Even Degrees

Consider an Euler circuit and a vertex \(v\). Each time the circuit arrives at \(v\), it also leaves \(v\), so these visits use incident edges in pairs. This pairing includes the starting vertex: because the route is closed, its final arrival pairs with its initial departure. Since the circuit uses every edge exactly once, every edge-end incident with \(v\) belongs to exactly one such pair. Therefore \(\deg(v)\) is even. This proves the necessary direction.

This argument concerns a circuit, not an open Euler trail. In an open trail the starting and ending vertices are not paired in the same way, so their degrees need not be even. Here the route is closed, which is essential to the parity argument.

Building and Splicing Closed Trails

To prove the converse, first consider a graph in which every degree is even. Start at a vertex with an incident edge, and keep extending a trail using edges not already used by that trail whenever possible. The graph is finite, so this process must stop. The key point is that it cannot stop at a vertex different from its starting vertex.

Proof. Let \(W\) be such a maximal trail, starting at \(x\) and ending at \(y\). Suppose that \(y\ne x\). Among the edges of \(W\), the number incident with \(y\) is odd: each visit to \(y\) before the final endpoint pairs an arrival with a departure, while the final arrival has no departure in \(W\). The total degree of \(y\) in the graph is even, so the number of incident edges not used by \(W\) is odd and therefore positive. One of those unused edges could extend \(W\) at \(y\), contradicting maximality. Thus \(y=x\), and \(W\) is closed. \(\square\)

The same argument applies when we work only with edges that remain unused. If a closed trail has already been constructed, it uses an even number of edge-ends at every vertex: every arrival on the closed trail pairs with a departure. Subtracting these used incidences from the even degree in \(G\) leaves an even number of unused incidences at each vertex. Consequently, any maximal trail made from unused edges, if started at a vertex incident with such an edge, also closes.

Here is why a closed trail made from unused edges can be joined to the one already built. If the new trail starts and ends at a vertex \(z\) on the existing circuit, write the existing circuit as a route that reaches \(z\), continues around its remaining edges, and returns to its starting point. Insert the new closed trail at \(z\), between the part that reaches \(z\) and the part that leaves \(z\). The resulting route is closed and uses each edge of the two trails exactly once, because the new trail uses only previously unused edges.

Proof of the Characterization

Proof. The necessary direction was proved above: if \(G\) has an Euler circuit, every vertex has even degree.

For the converse, assume that \(G\) is connected, has at least one edge, and every vertex has even degree. Choose a vertex incident with an edge. Starting there, extend a trail along unused edges until it cannot be extended. The lemma shows that this trail is closed; call it \(T\).

If \(T\) uses every edge, it is an Euler circuit and we are done. Otherwise, consider the set \(S\) of vertices that occur on \(T\). There must be an unused edge incident with some vertex of \(S\). To prove this, suppose there were no such edge. Every edge incident with a vertex of \(S\) would then be used by \(T\), and the other endpoint of each such edge would also lie in \(S\). If there were a vertex outside \(S\), connectedness would give a path from that vertex to a vertex in \(S\). The first edge on this path that enters \(S\) would be incident with \(S\), have its other endpoint outside \(S\), and could not be used by \(T\), a contradiction. Thus \(S=V(G)\). But then an unused edge, which exists by assumption, has endpoints in \(S\) and is incident with \(S\), again a contradiction.

Choose a vertex \(z\in S\) incident with an unused edge. The unused edges have even degree at every vertex: the original degree is even, and the closed trail \(T\) uses an even number of incidences at each vertex. Starting at \(z\), take a maximal trail using only unused edges. The lemma, applied to this graph of unused edges, shows that the new trail is closed. Splice it into \(T\) at \(z\). The result is a larger closed trail, with no repeated edges.

If this larger trail still omits edges, repeat the argument: connectedness gives a vertex on the trail incident with an unused edge, and the unused-edge trail from that vertex closes and can be spliced in. Each splice adds at least one edge to the closed trail. Since \(G\) has finitely many edges, after finitely many splices the resulting closed trail uses every edge exactly once. It is an Euler circuit. This proves the converse and the theorem. \(\square\)

Worked Constructions

Common Pitfall: Even Degrees Are Not Enough Without Connectivity

Do not apply the theorem after checking degrees alone. For example, let \(G\) have \(V=\{1,2,3,4,5,6\}\) and \(E=\{12,23,31,45,56,64\}\). Every vertex has degree \(2\), but the graph consists of two separate triangles. No trail can use edges from both components: moving along a walk cannot leave one component because there is no edge joining it to the other. Therefore this graph has no Euler circuit.

The theorem requires both conditions: all degrees must be even, and the graph must be connected. A useful way to remember the proof is that even degrees allow a trail to close, while connectedness ensures that a circuit which omits edges can still be enlarged by splicing in another closed trail.