Erdös-Gyárfás Conjecture for Cubic Planar Graphs

Christopher Carl Heckman, Roi Krakovski


In 1995, Paul Erdös and András Gyárfás conjectured that for every graph of minimum degree at least 3, there exists a non-negative integer $m$ such that $G$ contains a simple cycle of length $2^m$. In this paper, we prove that the conjecture holds for 3-connected cubic planar graphs. The proof is long, computer-based in parts, and employs the Discharging Method in a novel way.


Erdös-Gyárfás Conjecture; Cycles of prescribed lengths; Cubic planar graphs

Full Text: PDF