Wormald's conjecture, posed decades ago, predicted that the edges of any cubic graph (a graph where every vertex connects to exactly three others) can always be split into two groups, each forming an isomorphic "spanning linear forest," meaning a collection of paths that together touch every vertex. The conjecture seemed plausible and resisted resolution for a long time. This paper presents a concrete counterexample showing the conjecture is false.
The counterexample is a 16-vertex graph built by combining two well-known smaller graphs: the complete bipartite graph on six vertices called K(3,3), and a specially constructed 10-vertex graph assembled from modified copies of another classic graph called K4. The authors show that no matter how you try to divide the edges of this combined graph into two isomorphic spanning linear forests, you run into an unavoidable contradiction involving parity. Essentially, any valid partition would force every single-color connected piece to have an even number of vertices, but the structure of the graph contains a region with five vertices that cannot be carved up that way. By repeatedly attaching copies of K4, the authors extend this into an infinite family of counterexamples, one for each size of the form 16 plus a multiple of 4.
There is an important caveat: the counterexample is a disconnected graph, meaning it falls apart into separate pieces. Whether the conjecture holds for connected cubic graphs remains an open question. The authors also verified their entire family of counterexamples using Lean, a formal proof assistant software, which provides a machine-checked guarantee that the mathematics is correct and relies on no hidden assumptions.