A walk that splices in its own detours

Seven bridges found the obstruction: a walk that crosses every edge of a connected graph exactly once can pass through a vertex only by arriving and leaving, which uses its edges in pairs, so every vertex except the two ends must have an even number of edges. Königsberg had four vertices of odd degree, and no walk. Euler proved that in 1736.

He also said that the condition was sufficient — that any connected graph with every degree even has a closed walk using each edge once, and any with exactly two odd degrees has an open one — and did not prove it. The proof was published in 1873 by Carl Hierholzer, who had died two years earlier; it was reconstructed by a colleague from what Hierholzer had described in conversation. The necessary half is an obstruction, a reason something is impossible. The sufficient half has to build something, and what Hierholzer supplied is a procedure that builds it.

Walk until stuck #

The procedure starts anywhere and does the most naive thing possible: at each vertex, leave by any edge not yet used. It makes no plan and looks no further ahead than the next edge. Eventually it arrives somewhere with no unused edge to leave by, and stops.

The first observation is where it stops. In a graph whose degrees are all even, the naive walk can only get stuck at the vertex it started from. Take any other vertex $v$. Every earlier visit to $v$ arrived by one edge and left by another, using two; the walk has now arrived again, using one more. So the number of $v$’s edges used so far is odd. Since $v$ has an even number of edges, at least one is unused, and the walk can leave. Only the starting vertex escapes this argument, because its first edge was a departure with no arrival to pair it with.

This is exactly Euler’s argument for the necessary half, read in the other direction. Euler used the pairing of arrivals with departures to show an odd vertex must be an end. Hierholzer used it to show an even vertex cannot be one — so the only dead end the naive walk can reach is home.

In the hero figure the first walk leaves A, goes to B and C, climbs through E and F to D, and returns to A, stuck, having used six of the nine edges. Every vertex it passed was left by an edge; the only place it could fail to leave was A. The result is a closed walk. It is not the whole answer, because three edges — the triangle in the middle — were never touched.

Splice in a detour #

The second step handles the leftover edges. Among the vertices on the closed walk, find one that still has an unused edge; in the figure it is B. Start the naive walk again from there, on unused edges only. By the same argument it can only get stuck back at B, so it returns as another closed loop: B, D, E, B. Now splice: travel the first walk up to B, go round the new loop, and continue the first walk from B where it left off. The result is a single closed walk using all the edges of both.

Repeat until no vertex on the tour has an unused edge. At that point every edge of the graph is used — any unused edge would, by connectedness, lie on a path from some vertex of the tour, and the first vertex along that path would have an unused edge. The final circuit in the hero figure is numbered: A to B is edge 1, the detour round the triangle is edges 2, 3 and 4, and the rest of the first walk is edges 5 to 9.

The second example shows a subtlety in “splice in a loop”. The detour from O does not stop after one triangle, because arriving back at O it still finds unused edges and keeps going; it only stops when it arrives at O with nothing left, which is after both remaining triangles. A detour is itself a closed walk that can pass through its own starting point several times, and the splicing does not care. The procedure never backtracks and never has to undo anything — each edge is walked once, in the order it is found, and the whole construction takes a number of steps proportional to the number of edges.

An even graph is a union of cycles #

There is a second way to say the same thing, which strips out the walking and keeps only the structure.

In a graph where every degree is even, a walk on unused edges never meets a dead end until it repeats a vertex, and the stretch between the two visits to that vertex is a cycle. Remove the cycle. Every vertex on it loses exactly two edges, so every degree is still even, and the argument applies again to what is left. An even graph is exactly a graph whose edges can be split into edge-disjoint cycles — a statement Oswald Veblen made in 1912, and the conversational form of Euler’s condition that most modern proofs start from.

Hierholzer’s procedure and Veblen’s decomposition are the same fact seen twice. The loops that Hierholzer splices together are cycles, or unions of cycles, and gluing cycles together where they share a vertex is what splicing does. Seen as a decomposition, the even-degree condition becomes almost obvious: a graph that falls apart into loops can be traversed by going round each loop and switching loops wherever two touch, and connectedness guarantees that every loop is reachable by a chain of touches from every other.

The walk that does need a plan #

Hierholzer’s naive walk makes no attempt to avoid getting stuck early, and fixes the damage afterwards by splicing. An older rule avoids the damage in advance.

Fleury’s rule, published in 1883, says: at each step, never cross an edge whose removal would disconnect the edges still unwalked, unless there is no other choice. In the figure, the walk arrives at X with three choices. The edge back to A is the one the naive walk took, and it is a mistake: once walked, A’s last edge is used and the right-hand triangle can only be reached through X, which the walk has left for good. Fleury’s rule sees that the edge X–A is a bridge of the remaining graph and goes into the right-hand triangle first.

The two approaches differ in the work they do. Fleury’s rule never needs to splice, but checking whether an edge is a bridge means examining the remaining graph at every step, which costs far more than the step itself. Hierholzer’s walk examines nothing and repairs its mistakes by splicing, and the repair is cheap. Walking carelessly and splicing afterwards is faster than walking carefully, a small instance of a pattern that recurs throughout the design of procedures: it is often cheaper to allow a mistake and correct it than to prevent it.

Two odd vertices, and an imaginary bridge #

Euler’s claim had a second half: with exactly two odd vertices, there is an open walk from one to the other. That does not need a new construction.

Add one imaginary edge between the two odd vertices. Both now have even degree, every other vertex is unchanged, and the graph has a circuit. Go round it starting just after the imaginary edge, and stop just before crossing it again: what remains is a walk that uses every real edge once and runs from one odd vertex to the other. The figure does this for Kaliningrad, which lost two of Königsberg’s seven bridges in the Second World War and now has five, with exactly two odd landmasses — so the walk the citizens of Königsberg could not find is possible in the city today, and runs from the island to the eastern landmass.

The same trick extends further. A graph with $2k$ odd vertices can be covered by $k$ walks and no fewer: pair the odd vertices, add an imaginary edge for each pair, take the circuit, and cut it at every imaginary edge. The number of odd vertices is always even — every edge adds two to the sum of degrees, a count that the argument about more things than boxes places in the same family as the pigeonhole principle — so the pairing is always possible, and $k$ walks it is.

Every edge twice, in any graph at all #

The condition “every degree even” looks like a restriction on which graphs have circuits. There is a way of using it that works for every connected graph whatsoever. Replace each edge by two parallel copies. Every degree doubles, so every degree is now even, and the doubled graph has a circuit — which, read back in the original graph, is a closed walk that crosses every edge exactly twice.

That is the maze-explorer’s theorem. Anyone who walks each corridor of a maze exactly twice returns to the entrance having seen everything, and such a walk always exists. Gaston Tarry published a rule in 1895 that finds one without a map, using only marks left at the junctions, and Charles Trémaux’s older rule for mazes is a version of the same idea. The walk can even be arranged to cross each corridor once in each direction, which is what the splicing gives if the two copies of each edge are oriented oppositely: the doubled graph is then a directed graph with as many edges in as out at every vertex, and Hierholzer’s procedure applies unchanged.

Twice is the price for a graph with no conditions, and it is far more than most graphs need. A graph whose degrees are all even needs every edge once; a graph with a few odd vertices needs only a few edges twice. Which edges, and how few, is the problem of a postman who must walk every street of a district and return, and it has an exact answer: the streets a postman walks twice are the cheapest set of paths joining the odd vertices in pairs. The doubling argument is the crude upper bound; the pairing is the exact one.

The doubling also explains why Euler’s condition, unlike the condition for visiting every vertex, is so forgiving: an even graph is an ordinary graph in which the choice of which edges to double has already been made — none — and the parity count confirms that no doubling is needed. The same Euler who wrote the bridges paper found another parity-like count, vertices minus edges plus faces, for polyhedra; both are numbers that a graph’s local structure fixes and that constrain what can be done with it globally.

Where the same construction reappears #

The walk-and-splice procedure is not special to bridges. Every word once, around a cycle used it to build de Bruijn sequences: the graph there is directed, each vertex a word, each edge an overlap, and the condition for a circuit becomes “every vertex has as many edges in as out”, which the de Bruijn graph satisfies by construction. The proof that the directed condition suffices is Hierholzer’s, word for word, with “arrive” and “leave” meaning in-edge and out-edge. Every necklace, in order then found a greedy rule that happens never to need a splice on that particular graph — which is the exception, not the rule, as the two triangles above show.

The contrast with a walk that changes one thing at a time is the sharpest in the subject. There the question was a walk visiting every vertex once, a Hamiltonian cycle, and it looks like a small variation on visiting every edge once. It is not. No condition as simple as “every degree even” decides whether a Hamiltonian cycle exists, no splicing procedure builds one, and the general problem is among the standard hard problems of computation. Euler’s condition is local — it can be checked one vertex at a time — and the construction is too; the Hamiltonian question is global, and nothing local answers it.

What the drawings cannot show #

Connectedness. Every graph drawn here is connected, and the construction needs it: an even graph in two separate pieces has no single circuit, and the procedure would finish the piece it started in and stop. The figures do not show the argument that the final tour reaches every edge, which is where connectedness is used, because in a small connected drawing the conclusion is visible and the argument looks unnecessary.

The choices. The naive walk takes “the first unused edge”, and the figures fix an order on the edges so that the walk is determined. Any other order works just as well and gives a different circuit. How many different circuits a graph has is a separate and much harder question, and the figures, which show one circuit each, say nothing about it.

That stuck means home. The first panel of the hero figure shows a walk that stalled at its start. That it could not have stalled anywhere else is the parity argument, and it is the whole of the proof; the picture shows the outcome of the argument on one graph, which a reader could suspect was chosen to make it work.

Still open: counting the circuits approximately #

Finding one Eulerian circuit is easy, as the construction shows. Counting them all is a different matter. For directed graphs there is an exact formula, the BEST theorem — a determinant times a product of factorials, from de Bruijn, van Aardenne-Ehrenfest, Smith and Tutte — which is how the circuits of the de Bruijn graph are counted. For undirected graphs no such formula exists: Graham Brightwell and Peter Winkler showed in 2005 that counting the Eulerian circuits of an undirected graph exactly is as hard as the hardest counting problems of its kind.

The contrast with ordinary walks is instructive. Walks of a given length, with no restriction on repeating edges, are counted exactly by the powers of the graph’s adjacency matrix, as a matrix that counts the returns used them; it is the requirement that each edge be used exactly once that makes the count hard, because it couples every step of the walk to every other.

That leaves approximate counting. For some classes of graphs — those with many edges at every vertex, for instance — a random procedure is known that estimates the number of circuits to within any required accuracy in a reasonable time. For undirected graphs in general, whether the number of Eulerian circuits can be approximated efficiently is not known. It is a question about the most classical object in graph theory, and it sits exactly on the line between the easy question of finding one circuit and the hard question of counting them exactly.

A proof that is a procedure #

Euler’s half of the theorem is an obstruction, proved by pairing arrivals with departures. Hierholzer’s half is a construction, proved by the same pairing read the other way: a walk in an even graph can only stall where it started, so any walk is a closed loop, and any leftover edges hang off the loop as further loops that can be spliced in.

The construction is careless by design. It does not look ahead, as Fleury’s rule does, and it pays for its carelessness with a splice that costs almost nothing. It extends to two odd vertices with one imaginary edge, to directed graphs with in and out in place of arrive and leave, and to the de Bruijn sequences with no change at all — and it stops, sharply, at the question of visiting vertices instead of edges, where no procedure of this kind is known.