Hušek–Šámal's exponential circuit double cover conjecture

Let GG be a 22-connected cubic graph on nn vertices. A circuit double cover (CiDC) is a finite family of connected 22-regular subgraphs of GG such that every edge belongs to exactly two members of the family.

Hušek–Šámal's conjecture. The graph GG has at least

2n/212^{n/2-1}

CiDCs.

This is a quantitative strengthening of the cycle double cover problem. The bound is proved in the source for 22-connected 33-edge-colorable cubic graphs and is known to be tight for Klee graphs, while the general conjecture remains open.

Sources & referencesView supporting material

Primary source

Radek Hušek and Robert Šámal, “Exponentially Many Circuit Double Covers”, arXiv:2607.24724 (2026).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.