Every edge on exactly two cycles

The streets a postman walks twice doubled some of a town’s streets so that a postman could walk them all in one round. Double every street and the postman’s problem is trivial: every junction has even degree, an Euler circuit exists, and a walk that splices in its own detours finds it. But the circuit may walk a street and then immediately walk it back, and a circuit of the doubled graph breaks into pieces that are not all honest loops.

The essay ended on a stronger demand. Can the edges of a graph be covered by a collection of cycles — closed paths that never revisit a point — so that every edge lies in exactly two of them? A cycle cannot walk an edge and back, so such a collection doubles every street with no retracing anywhere. George Szekeres asked it in 1973 and Paul Seymour independently in 1979. The question is easy to test on any particular graph, small enough to try by hand on a graph of ten points, and it has outlasted almost every other problem of its generation in graph theory.

The cycle double cover conjecture says that every graph without a bridge has one. A bridge — an edge whose removal cuts the graph in two — lies on no cycle, so it has to be excluded; the conjecture is that nothing else can go wrong. This essay builds covers for the graphs that make it hardest, explains where the easy cases come from, and describes why a proof has resisted forty-five years of work.

Why doubling every edge is not enough #

A graph in which every point has even degree splits into cycles — that is Oswald Veblen’s theorem of 1912, and it is the other face of Euler’s: walk from any point without reusing an edge and a closed loop must eventually appear, remove it, and repeat. Seven bridges is where the even-degree condition first mattered.

Double every edge of a connected graph and every degree becomes even, so the doubled graph splits into cycles. But the doubled graph has two parallel copies of each edge, and one of the “cycles” Veblen’s theorem may produce is the pair of copies of a single edge — a loop of length two, which in the original graph is walking an edge and straight back. A cycle double cover is exactly a splitting of the doubled graph into cycles that never uses both copies of an edge in the same cycle. The conjecture is that this extra demand can always be met once bridges are excluded.

That framing explains why the problem sits next to the postman’s. The postman may repeat streets freely and wants to repeat as few as possible; the double cover repeats every street exactly once and wants the repetition to come in honest loops. The postman’s problem is solved by a matching and runs in polynomial time. The double cover problem is not even known to have a solution in every case where it could.

Five cycles for the Petersen graph #

The Petersen graph has ten points, each joined to three others, fifteen edges and 57 cycles. A double cover must use fifteen edges twice each, thirty edge-slots in all, and the search found five cycles of 5, 8, 6, 6 and 5 edges that do it — the outer pentagon, a pentagon of inner edges and three cycles that weave between the rings. Every smaller collection of cycles was tried and failed, so five is the minimum for this graph.

The search is simple. List every cycle of the graph. Pick the edge that is still short of two cycles and has the fewest cycles available to extend it, try each of those cycles in turn, and back up whenever some edge would be used three times. For the Petersen graph the first cover appears within 27 steps; proving that no four-cycle cover exists takes a little over sixteen hundred.

The Petersen graph is the natural first test because it breaks so many things. It is the smallest graph with three edges at every point and no bridge whose edges cannot be coloured with three colours so that each point sees all three. It is not planar, as the crossings a graph cannot avoid showed for graphs of its kind. It has no cycle through all ten points. It is also one of the Moore graphs of as many points as two steps allow, as symmetric as a graph with three edges at each point can be. Each of those failures removes one of the easy proofs of a cover, described below, and the cover exists anyway.

Faces, when the graph can be drawn flat #

For a graph drawn in the plane without crossings, a cover is visible at once. Each edge separates exactly two regions — the faces on its two sides — and if the graph has no bridge, the boundary of each face is a cycle. So the faces form a cycle double cover: every edge on the boundary of exactly two of them. The cube in the figure has six faces, each a square, and each of its twelve edges borders two.

That argument is the reason the conjecture is believed and the reason it is hard. It reduces the question to a question about drawings: if every bridgeless graph could be drawn on some surface — a sphere, a torus, a surface with more handles — so that every face is bounded by a cycle, the faces would give a cover. The fewest corners a surface needs counted the faces of graphs drawn on surfaces by Euler’s formula; here what matters is not how many faces there are but whether each face’s boundary is a genuine cycle. That stronger statement, the strong embedding conjecture, implies the cycle double cover conjecture and is open too.

For a graph with a cycle through all its points — a Hamiltonian cycle — a cover can also be built directly, using the Hamiltonian cycle once and repairing the rest with a parity argument. Every graph with four edge-disjoint routes between any two points is covered as well, by a theorem about flows. The Petersen graph has neither property, which is why it had to be checked by search.

The one thing that must be excluded #

A bridge is fatal for a simple reason. A cycle that crosses from one side of the bridge to the other must return, and the bridge is the only way back, so it would have to use the bridge twice — which a cycle, by definition, cannot. So no cycle passes through a bridge, and a graph with one has no cycle double cover, nor even a cover of each edge by one cycle.

The conjecture says this is the only obstacle. It is a remarkable kind of claim: a local, easily checked condition — no single edge disconnects the graph — would guarantee a global structure that no one knows how to build in general. Most conjectures of this shape in graph theory turn out to need more conditions than the obvious one; this one has survived every attempt to add a counterexample to the list.

Snarks, where a counterexample would live #

The hardest cases are known precisely. François Jaeger showed that a smallest graph with no cycle double cover, if one exists, must have exactly three edges at every point and must be a snark: its edges cannot be coloured with three colours so that each point sees all three, and it must avoid a few other simplifying features — no cycle shorter than five, no small set of edges whose removal splits off a cycle. The name, taken from Lewis Carroll by Martin Gardner in 1976, reflects how rare such graphs seemed; the Petersen graph is the smallest.

The reason for the restriction is that three-edge-colourable graphs are easy. Given a colouring with colours red, green and blue, the red and green edges together form disjoint cycles, as do the green and blue, and the blue and red. Those three collections cover each edge exactly twice — a red edge is in the red-green and blue-red collections — and a double cover by cycles follows at once. So only snarks can fail.

The cube shows the colouring argument at work. Its twelve edges can be coloured with three colours so that each point sees all three — colour each of the three directions of the cube with its own colour. The edges of any two directions together form two squares, disjoint from each other; the three pairs of directions give six squares in all, and each edge, lying in one direction, belongs to the two pairs that include that direction. Those six squares are exactly the six faces drawn in the second figure: for the cube, the planar cover and the colouring cover are the same cover.

The flower snarks, found by Rufus Isaacs in 1975, are an infinite family, and the one on twenty points has 1,444 cycles. The search found five of them that cover every edge twice, in 502 steps, including one long cycle through nineteen edges. Every snark that has been examined has a cycle double cover, including all snarks up to thirty-six points, which have been generated and checked by computer.

Random graphs, covered easily #

Random graphs are no harder, and they are the natural place to look if a counterexample were common. Seventy-two random graphs with three edges at every point and no bridge, from ten to twenty points, all have covers, and the search finds them quickly — a few hundred steps at twenty points, against an average of over a thousand cycles to choose from. The number of cycles grows much faster than the effort needed, which says covers are plentiful: at every step there are many ways to continue, and a wrong turn is rarely fatal.

That is the frustrating feature of the problem. Nobody expects a counterexample among graphs anyone can write down, and nobody has a method that produces a cover without searching. The proofs for special classes each use a special structure — a drawing, a Hamiltonian cycle, a colouring, a flow — and a general graph has none of them.

Flows, and why four routes are enough #

The theorem for graphs with four edge-disjoint routes between every pair of points comes from flows, the same objects the bottleneck is the whole story used to move goods through a network, with the capacities removed. Give every edge a direction and a whole-number value, not zero, so that at every point what flows in equals what flows out. If every value can be kept between $-3$ and $3$, the graph has a nowhere-zero 4-flow, and a theorem of Jaeger’s turns such a flow into a cycle double cover: a nowhere-zero 4-flow is the same thing as a way of writing the edge set as the union of two even subgraphs, and those two with their symmetric difference cover every edge exactly twice.

Jaeger proved in 1979 that every graph with four edge-disjoint routes between every pair of points has a nowhere-zero 4-flow, and so a cover. Seymour proved in 1981 that every bridgeless graph has a nowhere-zero 6-flow, which is not enough for a cover by this route. Tutte conjectured in 1954 that 5 always suffices, and that conjecture, like this one, reduces to snarks and is open. The Petersen graph has a nowhere-zero 5-flow and no 4-flow — which is another way of saying it is a snark, and another reason the colouring argument had to be replaced by a search.

Five cycles are always enough, conjecturally #

The covers in the figures all have five cycles, and that is not a coincidence of these graphs. Uldis Celmins and Michel Preissmann conjectured independently in the early 1980s that every bridgeless graph has a cycle double cover using at most five collections of disjoint cycles. Three suffice for the three-edge-colourable graphs, by the colouring argument; the Petersen graph shows that fewer than five do not suffice in general, and the search above found its minimum of five exactly.

The five-cycle version is stronger than the original, and a proof of it would settle the original. It is equally open. There is a still stronger form, in which the cycles can be oriented so that every edge is traversed once in each direction — an oriented cycle double cover — and it too is conjectured for every bridgeless graph and known only in special cases. Each strengthening makes the statement more rigid, and none has yielded to the methods that settle the special classes.

Where the conjecture sits among its neighbours #

The cycle double cover conjecture belongs to a cluster of problems about bridgeless graphs whose easy cases come from colourings and whose hard cases are snarks. The four-colour theorem, which four colours and a proof nobody can read described, is equivalent to the statement that every bridgeless planar graph with three edges at every point is three-edge-colourable — which is why planar snarks do not exist. Tutte’s five-flow conjecture, that every bridgeless graph has a nowhere-zero flow with values below five, is another member of the cluster, and it too reduces to snarks.

What unites them is that three-edge-colourability makes each of them easy, and snarks are exactly the graphs where it fails. A theory of snarks deep enough to settle one of these conjectures would probably settle several; no such theory exists, and snarks remain a zoo of examples — the Petersen graph, the flower snarks, the Blanuša snarks, the Goldberg snarks — rather than a family with a structure theorem.

Still open: every bridgeless graph #

The cycle double cover conjecture is open. It is known for planar graphs, for graphs with a Hamiltonian cycle, for graphs with four edge-disjoint routes between every pair of points, for three-edge-colourable cubic graphs, for all snarks up to thirty-six points, and for many special families. A minimal counterexample would be a snark with no cycle shorter than twelve — the lower bound on its girth has been pushed up repeatedly — and with a long list of other forbidden features.

The difficulty is that a cover is a global object assembled from local pieces, and every known method of assembly depends on a global structure — a drawing, a colouring, a flow — that a snark lacks by definition. The Petersen graph shows the problem in miniature: it has a cover, found by trying cycles, and no structural reason anyone can give for why that cover had to exist.

What the figures cannot show #

Every cover drawn was found by exhaustive backtracking over the graph’s full list of cycles and checked edge by edge. The minimum of five for the Petersen graph is proved by that search, which tried every smaller collection; the flower snark’s cover of five is shown without a proof that four cannot work, since that search takes far longer. The random graphs are samples from one simple model, and every one of them is covered.

The method also scales badly in a specific way. The search starts by listing every cycle, and the number of cycles in a graph with three edges at each point roughly doubles with every two points added — from 57 in the Petersen graph to over a thousand at twenty points, as the last figure shows. A graph of fifty points can have millions of cycles, and listing them is already the expensive part.

Nothing here bears on graphs beyond the few dozen points the searches reach, and a counterexample, if one exists, is already known to be far larger. The figures show the conjecture holding in every case they touch, which is also true of every figure anyone has drawn in forty-five years.