Small graphs without power-of-two cycles: a lower bound of 24, a correction to a construction of Exoo, and explicit bounds for f(k)
Abstract
The Erdos-Gyarfas conjecture states that every graph with minimum degree at least 3 contains a cycle whose length is a power of two. We prove by a SAT-based exhaustive search, certified by DRAT proofs, that every graph with minimum degree at least 3 on at most 23 vertices contains a cycle of length 4 or a cycle of length 8; consequently any counterexample has at least 24 vertices, improving the previously published bound of 16, and the smallest graph of minimum degree 3 with no 4-cycle and no 8-cycle has exactly 24 vertices. We show that the lemma underlying Exoo's 450-vertex construction for the bound f(5) at most 450 is false: the Tutte-Coxeter graph contains 8-cycles alternating between outer and chord edges, and the graph as specified contains 32-cycles. We repair the construction and verify the corrected graph, so the bound stands. We also give an exact window calculus for vertex-replacement constructions, prove that f(k) is at most 15 times the order of the smallest known cubic graph of girth 2 to the power (k-2) plus 1 for all k at least 4 (in particular f(6) is at most 32640, the first bound for f(6)), and show that Exoo's 78-vertex witness for f(4) at most 78 is optimal among gadget designs on bases with at most 12 vertices. All graphs, scripts and certificates are archived at doi:10.5281/zenodo.22180583.
Related
- Extremal graphs without cycles of length 0 modulo 4
- On graphs without cycles of length $0$ modulo $3$ or $4$ modulo $6$
- Total-coloring of planar graphs with maximum degree 6 and without prescribed 4-cycles
- Torsion Cycles in Projective Threefolds:From Serre's Construction to Artin-Mumford
- Polynomial Length Cycles In Tough Graphs
BibTeX
@misc{garcia2026small,
title = {{Small graphs without power-of-two cycles: a lower bound of 24, a correction to a construction of Exoo, and explicit bounds for f(k)}},
author = {Daniel Garcia},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.04686},
eprint = {2609.04686},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.04686},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Small graphs without power-of-two cycles: a lower bound of 24, a correction to a construction of Exoo, and explicit bounds for f(k)
AU - Daniel Garcia
PY - 2026
DA - 2026/09/04
PB - arXiv
DO - 10.48550/arxiv.2609.04686
UR - https://arxiv.org/abs/2609.04686
AB - The Erdos-Gyarfas conjecture states that every graph with minimum degree at least 3 contains a cycle whose length is a power of two. We prove by a SAT-based exhaustive search, certified by DRAT proofs, that every graph with minimum degree at least 3 on at most 23 vertices contains a cycle of length 4 or a cycle of length 8; consequently any counterexample has at least 24 vertices, improving the previously published bound of 16, and the smallest graph of minimum degree 3 with no 4-cycle and no 8-cycle has exactly 24 vertices. We show that the lemma underlying Exoo's 450-vertex construction for the bound f(5) at most 450 is false: the Tutte-Coxeter graph contains 8-cycles alternating between outer and chord edges, and the graph as specified contains 32-cycles. We repair the construction and verify the corrected graph, so the bound stands. We also give an exact window calculus for vertex-replacement constructions, prove that f(k) is at most 15 times the order of the smallest known cubic graph of girth 2 to the power (k-2) plus 1 for all k at least 4 (in particular f(6) is at most 32640, the first bound for f(6)), and show that Exoo's 78-vertex witness for f(4) at most 78 is optimal among gadget designs on bases with at most 12 vertices. All graphs, scripts and certificates are archived at doi:10.5281/zenodo.22180583.
ER -