Cycle Double Cover
A graph is a set of dots, called vertices, joined by lines, called edges. A cycle is a closed loop of edges that visits each of its vertices once. A bridge is an edge whose removal cuts the graph into more parts. A bridge cannot be in a cycle, because a loop that crosses it has no other way back.
A cycle double cover is a list of cycles in which every edge of the graph appears exactly twice. A graph with a bridge cannot have one. The cycle double cover conjecture says that this is the only obstacle. It says that every graph with no bridge has a cycle double cover.
Some graphs make this easy. Draw a graph on paper with no crossing edges. The edges cut the paper into regions, and the area outside the drawing counts as one region. Each edge has one region on each side. So the outlines of the regions use each edge exactly twice. An outline that touches itself at a vertex splits into smaller cycles.
A cube is one example. You can flatten its 12 edges onto paper with no crossings, and its 6 faces become the regions. Each face has 4 edges, which gives 24 uses in total, and .
The hard graphs are those that you cannot draw on paper without crossings. They have no regions to use. The Petersen graph in the figure is the best-known example. It still has a double cover: six cycles of 5 edges each, and .
There is another way to say the same thing, with colors. Give each edge exactly two colors, so that each color appears an even number of times at each vertex. Now look at the edges of one color. If you walk along them, you can always leave a vertex that you enter, so these edges split into closed loops. Each edge has two colors, so it lies in two loops.
OpenAI reports a proof, which it credits to GPT-5.6 Sol Ultra. The proof finds such a coloring with linear algebra, the algebra of tables of numbers, starting from an older theorem about flows on graphs. Graph theorists Jim Geelen and Sang-il Oum have each written out the argument. Oum writes that it can be taught to advanced undergraduate students.