The Erdos-Gyarfas conjecture is a long-standing problem in graph theory. It predicts that every graph where every vertex connects to exactly three others (called cubic graphs) must contain a cycle whose length is a power of 2, meaning 4, 8, 16, 32, and so on. Proving this for all cubic graphs has proven very difficult, so researchers often focus on special families. This paper focuses on cubic bipartite graphs, which are cubic graphs whose vertices can be split into two groups where all edges run between the groups rather than within them.
The main result is a computer-verified proof that every cubic bipartite graph with 58 or fewer vertices contains a cycle of length 4, 8, or 16. This means if a counterexample to the conjecture exists within this family of graphs, it must have at least 60 vertices. This doubles the previous best lower bound of 30 vertices, which is a significant improvement. The approach is clever: the authors first use a theoretical observation to show that any cubic bipartite graph below 62 vertices that avoids 4- and 8-cycles must contain a 6-cycle. They then reframe the problem using a geometric structure called a configuration, which transforms that 6-cycle into a useful local pattern. From there, they show only two possible structural starting points exist, and they exhaustively search all graphs that can be built from those starting points.
Because the result depends on a large computer search, the authors took extra care to make it trustworthy. They implemented two completely independent verification programs using different methods, and they also produced a static certificate, essentially a stored proof that any other program can check without repeating the full search. All source code, certificates, and instructions for reproducing the results are publicly archived alongside the paper, meeting high standards for computational proof in mathematics.