Towards a more structured search for Erd\H{o}s-Gy\'arf\'as counter-examples
In the authors' words
The Erd\H{o}s-Gy\'arf\'as conjecture posits that every graph with minimum degree at least three contains a cycle of length some power of two. We prove a few simple structural properties for any minimal counter-example to this conjecture. In particular, the fraction of its vertices of degree three must be greater than , thus improving on the prior bound of (Carr, 2026). Furthermore, it is either biconnected or the -clique-sum of two biconnected graphs. By exploiting some of these properties, we were able to verify the conjecture for every graph of order at most , every bipartite graph of order at most , and every cubic graph of order at most .
Main resultLimitation the authors admit
Appeared: Friday, September 25. arXiv. Preprint, not yet peer-reviewed.