A 60-Vertex Lower Bound for Cubic Bipartite Counterexamples to the Erdős-Gyárfás Conjecture
Abstract
A certified exhaustive computation shows that every simple cubic bipartite graph on at most 58 vertices contains a cycle of length 4, 8, or 16. Consequently, any cubic bipartite counterexample to the Erdos-Gyarfas conjecture has at least 60 vertices, improving the established published lower bound for this class from 30 to 60. The proof begins with a Moore-bound observation: below 62 vertices, a cubic bipartite graph avoiding 4- and 8-cycles must contain a 6-cycle. Viewing the graph as the Levi graph of a linear symmetric v3-configuration turns this 6-cycle into a Berge triangle. Up to symmetry, only two rooted extensions are possible. A complete restricted-growth search on at most 29 points exhausts both search trees. The computation is checked by two separately implemented exact procedures using different C16 oracles and by a static witness certificate. Source code, certificates, and reproduction instructions are archived with the paper.
Disclosure
“materially assisted the initial research, including developing computational and structural approaches, portions of the incidence-based code and preliminary arguments, running and interpreting computations, and an initial literature audit. OpenAI Codex subsequently assisted with code and artifact auditing, reproducibility checks, additional verifiers and certificates, integration of the triangle-rooted method, and drafting and editing the manuscript and documentation. A custom clos”
PDF page 9
- Classification
- Drafting limited passages
- Multiplier
- 5
- Verified
Structural counts
Count notes
- Source counts use the expanded primary TeX file Tranquilli_2026_Erdos-Gyarfas_60-Vertex_Lower_Bound.tex.
- Appendix pages include the first PDF page with an explicit Appendix heading through the final page.