In graph theory, some problems ask whether a network can be divided neatly in two. For cubic graphs—networks where every point connects to exactly three others—one long-standing conjecture made a particularly appealing prediction: when the graph has a number of vertices divisible by four, its edges can be split into two matching collections of paths. A new counterexample overturns that expectation with just 16 vertices. Its obstruction is not a tangle too intricate to see, but a parity mismatch hiding at a single bridge.
First, the terms. A linear forest is a collection of separate paths, with no loops or branching. A spanning one includes every vertex in the graph, even if some are isolated. Two such forests are isomorphic when their paths have the same lengths—in other words, when their collections of component sizes match. The conjecture asks for a cubic graph’s edges to be colored red and blue so that each color makes a spanning linear forest, and the red and blue forests are twins in this precise sense.
The basic challenge is already constrained: because every vertex has three edges, neither color can take all three without creating a branch. Earlier work established that cubic graphs can be split into two linear forests. Wormald’s sharper conjecture added the surprising symmetry requirement: not just two path collections, but two identical ones. That extra demand is where the counterexample strikes.
Its construction combines two small pieces. One is the complete bipartite graph K3,3, with three vertices on each side and every possible cross-connection. The other begins with two copies of the complete graph on four vertices. In each copy, one edge is split in two by inserting a new vertex. Then those two inserted vertices are joined by a fresh edge. That joining edge is a bridge: remove it, and the construction falls into two separate five-vertex halves.
This bridged piece has 10 vertices; together with K3,3’s six, the whole graph has 16. Each vertex still has three connections. The task is to find a red-blue edge coloring that gives each color a spanning forest of paths, with both forests having the same path sizes. The proof begins with what the coloring would force at every vertex: one red edge and two blue, or two red and one blue. Each color must touch every vertex, and neither can branch.
That local rule puts a tight limit on the K3,3 part. The two colors together use its nine edges. Counting the pieces of path in each color shows that one color must form a single path through all six vertices, while the other must break into two paths. Because the two colors complement each other in this small graph, those two paths have sizes four and two. So, inside K3,3, the two colors already have different path inventories: one gets a six-vertex path; the other, a four-vertex path and a two-vertex path.
Now the demand for matching forests reaches across the whole graph. The color with the four- and two-vertex paths inside K3,3 must also have a six-vertex path somewhere to match its rival. It cannot find one in K3,3, where its pieces are already fixed, so that path has to lie in the bridged section. The remaining four vertices there must form another path. The result is a global inventory of one six-vertex path, two four-vertex paths, and one two-vertex path. If the forests are isomorphic, both colors must share that inventory.
Here the bridge turns a bookkeeping problem into a contradiction. Every path in the required inventory has an even number of vertices. But one color must omit the bridge, since the bridge can be colored only red or blue. For the color that leaves it out, every path in the bridged section stays entirely on one side or the other. Each side has five vertices. To cover those five vertices using only even-sized paths is impossible: adding even-sized groups can never make an odd total. So the two supposedly matching forests cannot exist.
The clash is striking because each part of the argument seems harmless on its own. The small bipartite graph fixes the paths that must appear; the bridge splits the other piece into odd-sized sides. Only when those constraints meet does the hidden trap snap shut. The example does not show that ordinary path decompositions fail. It shows that demanding the two decompositions be identical can make an otherwise plausible arrangement impossible.
Nor is the obstruction limited to one graph size. The author shows that copies of the complete graph on four vertices can be added to the construction, producing counterexamples with 16, 20, 24, and every larger vertex count increasing by four. In each added copy, both colors must form the same four-vertex path. Those matching additions cannot repair the original mismatch; remove them from the proposed pair of forests, and the impossible 16-vertex case remains.
The proof also comes with a machine-checkable formalization in Lean. The verification checks the possible edge subsets in K3,3 and then combines that finite accounting with the general parity argument. This is a way to audit the reasoning, not a computer search standing in for the explanation: the decisive contradiction is still the five vertices that cannot be covered by even-sized pieces.
There is an important boundary to the result. The counterexample is disconnected: K3,3 sits apart from the bridged component. Whether a connected cubic graph can provide the same kind of obstruction remains unresolved. So the conjecture’s failure exposes a precise weakness, not a universal breakdown. A small disconnected graph has shown that identical path decompositions are not guaranteed in every case—and that, in this puzzle, parity can be stronger than symmetry.
