Skip to content

Erdős Problem #64

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: falsifiable (not automatically the live result).
Subject areas: graph theory, cycles.

Read this status correctly

The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.

The question in plain language

If every vertex of a finite graph has at least three neighbors, must the graph contain a cycle whose length is a power of two: \(4,8,16,32,\ldots\)? This is the Erdős–Gyárfás conjecture.

The problem is unresolved. Its catalogue label FALSIFIABLE does not mean it has been disproved. It means that a single verified finite counterexample would refute the universal claim.

A small example

The complete graph \(K_4\) has four vertices, each connected to the other three. Its minimum degree is three, and it contains a four-cycle. Thus it satisfies the conjecture.

The word finite is crucial. An infinite tree can have every vertex of degree three but no cycles at all. Such a tree is not a counterexample to the finite-graph conjecture.

What is known

Liu and Montgomery proved that graphs of sufficiently large average degree contain cycles of power-of-two length. Their Corollary 1.3 covers sequences of even cycle lengths growing at most exponentially, including \(4,8,16,\ldots\). The underlying Theorem 1.1 gives every even cycle length in a long interval.

If the minimum degree is at least the theorem's sufficiently large threshold, then the average degree is also at least that threshold, so the conjecture holds. But this does not establish the conjecture at the original minimum degree three.

Erdős and Gyárfás also entertained a stronger possibility: for every large minimum-degree threshold, some graph might avoid all power-of-two cycle lengths. The high-average-degree theorem rules out that stronger speculation. It does not prove the original statement.

GCL's current state

The pinned catalogue and maintained Erdős #64 label the problem FALSIFIABLE, not proved or disproved. A formal statement file exists in the protected source snapshot, but this article does not assert a Lean proof or a semantic-fidelity check. The original GCL source assignment is #1333.

This is an unaccepted local draft. The catalogue's historical prize metadata does not imply any award decision.

The original issue contains an authenticated RESULT/1 source report. This is unadjudicated source evidence only, not independent mathematical certification or editorial admission.

What remains

A bounded computational task is to enumerate finite cubic graphs and test every simple cycle whose length is a power of two and at most the number of vertices. A candidate counterexample must come with a complete edge list, a verified minimum-degree calculation and a reproducible absence-of-cycle certificate. Finding no counterexample up to some size is only finite evidence.

A separate formal task is to encode the implication from a sufficiently large minimum-degree threshold to the known average-degree theorem, without replacing the unknown threshold by three.

Sources and claim boundaries

No counterexample, proof, Lean certification, prize award or editorial acceptance is claimed.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #1333 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
  • GCL triage: OUTSIDE_STRICT_OPEN_TRIAGE.
  • Formal-statement coverage: A provider statement was included in the pinned snapshot. Presence does not mean the statement or proof has been checked.
  • External mathematical status: consult current problem page and its dated bibliography.

Back to catalogue · Compendium introduction