Every Edge Gets Two Loops — A CDC Proof Playground

Skip the paperwork

Case CDC-001 · double-checked, literally

Every edge deserves two good loops.

A playful field guide to the Cycle Double Cover proof: turn a bridgeless graph into cubic paperwork, assign tiny XOR gremlins, then watch closed cycles emerge.

The theorem: Every finite bridgeless undirected graph has a collection of cycles covering every edge exactly twice.

Audit a graph<br>Show me the proof

Interactive explainer of the linked note, not an independent verification.

No edge left behind.<br>Also: no edge left alone.<br>×2

Interactive cube graph<br>Twelve edges show how many selected face cycles cover them: zero, one, or two.

Each badge is an edge’s cycle count. Green “2” = fully chaperoned. Facial boundaries work here because the cube is planar.

Edges exactly twice-covered<br>0 / 12

Front<br>Back<br>Top<br>Bottom<br>Left<br>Right

Do the paperwork for me<br>Emergency unstamp

Twelve edges await responsible adult cycles.

Flow x

Flow y

Shift t

z = x ⊕ y = 011

a · x<br>b · y<br>c · z

edge a

edge b

edge c

These are {t, t+x} , {t+x, t+z} , and {t, t+z} . In this world, “+” is XOR.

MOVE 01 / REDUCE<br>Make the graph cubic.

A standard reduction says it is enough to handle loopless cubic multigraphs. So every junction now has exactly three incident edges.

general bridgeless G<br>→ loopless cubic G

less graph, same problem

MOVE 02 / LABEL<br>Issue nonzero 3-bit IDs.

Use a nowhere-zero flow in Γ = F₂³. At each vertex the incident labels satisfy x + y + z = 0, with addition meaning XOR.

f(e) ≠ 000<br>x ⊕ y ⊕ z = 000

seven legal gremlins

MOVE 03 / PAIR<br>Give every edge two passengers.

Construct a two-element set Pe so each symbol s appears on either zero or two edges at every vertex. Local pairs are easy; endpoint agreement is the hard bit below.

|Pe| = 2<br>local count(s) ∈ {0, 2}

strict buddy system

MOVE 04 / SORT<br>Follow one passenger.

For each s, collect edges carrying s. Every vertex has degree zero or two, so that collection is a union of cycles. Each edge carries two symbols, so it appears twice overall.

Ms = {e : s ∈ Pe}<br>degMₛ(v) ∈ {0, 2}

cycles fall out

The bit that earns the theorem: endpoint couples therapy

The disagreement

The local recipe works at every vertex, but the two ends of an edge may assign it different passenger pairs. Give each vertex a shift tv, and each edge a one-bit “flip” εe. For e = uv, agreement becomes one linear equation:

tu + tv + εef(e) = de<br>Here de records the original mismatch. Solve all these equations at once and the local pairs glue into globally well-defined Pe’s.

Why a solution exists

Linear duality says the system can fail only if a dual witness η detects d while vanishing on every possible left-hand side. The local flow identities force each vertex’s contribution to equal the parity of its nonzero incident witnesses.

Now sum over all vertices: every nonzero edge witness appears once at each endpoint—twice. Over F₂, twice is zero. So no witness detects d, and the system is solvable.

Judge XOR’s ruling: “The prosecution counted every accusation twice. Case dismissed.”

Every edge gets two cycles. Nobody gets a bridge.

That is the proof’s shape. The paper has the exact bookkeeping in three brisk pages.

Open the serious version ↗