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

Abstract

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.