{"id":"arxiv/2609.04686","url":"https://arxiv.org/abs/2609.04686","tags":["math.CO"],"score":0,"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)","domain":"math.CO","source":"arxiv","authors":["Daniel Garcia"],"reviews":0,"subject":"math.CO","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-04","reactions":{}}