Bondy's small cycle double cover conjecture

Status partial medium confidence

Bondy's small cycle double cover conjecture (every bridgeless graph on n vertices has a cycle double cover of size at most n-1) remains open in full generality. Partial results have been established for planar graphs: Jooken, Seamone, and Zamfirescu (2025) prove the bound for planar 4-connected graphs and show every planar 2-connected cubic graph on n > 4 vertices has a CDC of size at most n/2. Notably, the parent CDC conjecture (every bridgeless graph has some cycle double cover) was apparently proved in 2026 via an OpenAI-announced proof with an exposition by Sang-il Oum, but his exposition explicitly notes that Bondy's n-1 bound does not follow immediately from those methods.

Cited literature (2)

• partial Counting Small Cycle Double Covers (2025)
  Jorik Jooken, Ben Seamone, Carol T. Zamfirescu · arXiv preprint · arXiv:2506.10604

  Proves Bondy's n-1 bound for planar 4-connected graphs and shows every planar 2-connected cubic graph on n > 4 vertices has a CDC of size at most n/2; does not resolve the full conjecture.

• survey A proof of the cycle double cover conjecture by OpenAI: An exposition (2026)
  Sang-il Oum · arXiv preprint · arXiv:2607.16356

  Expounds a 2026 OpenAI-announced proof of the parent CDC conjecture (every bridgeless graph has a cycle double cover); Section 9 explicitly notes Bondy's small CDC conjecture (at most n-1 cycles) does not follow from these methods.

Reviewer notes. Confidence is medium because paper content was assessed via WebFetch AI-model summaries rather than full PDF reads. The distinction between the parent CDC conjecture (Appendix A item 12, now apparently proved) and Bondy's strengthening (item 13, requiring at most n-1 cycles) is crucial: the Oum exposition of the 2026 CDC proof explicitly states the n-1 bound does not follow from those methods, so item 13 remains open. The 2025 paper 2506.10604 directly addresses the exact statement of Bondy's conjecture for planar graphs. This conjecture is strictly stronger than the OPG corpus record cycle_double_cover_conjecture, which appears now settled.

Auto-reviewed 2026-09-10 with claude-sonnet-4-6 (web search enabled).