Answers are grounded in this paper and cite their sources.
Uncovers structural properties of cubic vertices in minimal counterexamples, suggesting deeper insights into graph theory.
A minimal counterexample to the Erdős–Gyárfás conjecture is a graph of minimum possible order and, subject to that, minimum possible size, with minimum degree at least 3 and containing no cycle whose length is a power of 2. Carr recently showed that at least 4/7 of the vertices of any minimal counterexample have degree exactly 3. We observe that combining two structural facts already established in that work yields the stronger bound 2/3, and we prove an additional structural restriction: whenever the four edges leaving a pair of adjacent cubic vertices all end in vertices of degree at least 4, the pair has a unique common neighbor, and that common neighbor has degree exactly 4.
No takes yet. Share an insight, caveat, or question.
Andrew Bisch (2026) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: