A 60-Vertex Lower Bound for Cubic Bipartite Counterexamples to the Erd\H{o}s-Gy\'arf\'as 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.