Erdős-Gyárfás Conjecture

Definitions and mathematical statement

Shared notation.

Unless a section says otherwise, ${\mathbb{N}}=\{1,2,\ldots\}$, ${\mathbb{Z}}$ is the ring of integers, ${\mathbb{Q}},{\mathbb{R}},{\mathbb{C}}$ are the rational, real, and complex fields, $[N]=\{1,\ldots,\lfloor N\rfloor\}$, and $\log$ is the natural logarithm. For real functions of a parameter tending to infinity, $f\ll g$ and $f=O(g)$ mean $|f|\leq Cg$ eventually for some fixed $C$; $f\gg g$ reverses this comparison; $f=o(g)$ means $f/g\to0$; $f\sim g$ means $f/g\to1$; and $f\asymp g$ means both order bounds. A subscript on $O$ or $\ll$ specifies allowed constant dependence. The expression $n^{o(1)}$ in an upper bound means growth smaller than $n^\epsilon$ for each fixed $\epsilon>0$. Local definitions govern any exception, finite-field convention, or use of the same symbol for another object. An asymptotic claim is not automatically an effective algorithm.

Use finite simple graphs. The hypothesis is minimum degree at least three. A cycle is simple, so the possible power-of-two lengths start at $2^2=4$. The required exponent may depend on the graph; there is no proposed universal upper bound on that exponent. [S1] [S2]

Statement recorded in the supplied source.

Does every graph with minimum degree 3 contain cycles of lengths that are powers of 2? [S1]

Residual task reported by the archive.

The embedded review (2026-08-17) records: Settle the cubic/small-minimum-degree regime. [S1]

Short English statement

Must every finite graph of minimum degree at least three contain a cycle of length four, eight, sixteen, or another power of two?

Sources

• S1 ULAM.AI, UnsolvedMath, supplied problems.json, record 1417 (GRAPH-030), statement and background. The embedded literature-review date is 2026-08-17; that is the archive’s review date, not a fresh certification. Dataset landing page: https://huggingface.co/datasets/ulamai/UnsolvedMath.

• S2 Erdős-Gyárfás conjecture on graphs without long induced paths, arXiv:2410.22842 (2024). https://arxiv.org/abs/2410.22842. Bibliographic information from the supplied record.

• S3 Erdős-Gyárfás Conjecture for P10-free Graphs, arXiv:2308.05675 (2023). https://arxiv.org/abs/2308.05675. Bibliographic information from the supplied record.