The Erdos-Gyárfás Conjecture: From Cubic Blocks to Minimum Degree Three

We prove the Erdos-Gyárfás conjecture for increasingly general classes of graphs. Theconjecture asserts that every graph with minimum degree at least 3 contains a cycle whoselength is a power of 2. We establish this frst for cubic (3-regular) 2-vertex-connected blocks,then extend to all cubic graphs via block decomposition, and nally generalize to arbitrarygraphs with δ ≥ 3 and unbounded maximum degree Δ.Our approach introduces a Core Tendril Dichotomy that separates local cycle structureinto two regimes: either the neighborhood has rich cyclomatic content (Core), or it exhibitsa long corridor to the boundary (Tendril). In both cases, we establish an edge-local gap-2property: every edge participates in two cycles whose lengths differ by exactly 2. Combinedwith a regime-forcing argument and spectrum closure, this yields cycles of length 2k.For general degree Δ > 3, we introduce a terminal-anchored approach that routes allboundary attachments to a fixed terminal, avoiding connectivity assumptions on the exteriorregion. This technique may be of independent interest.