Graph theory · cycle lengths · minimum degree · cubic graphs

Erdős–Gyárfás Conjecture

Collaboration beta

Graphs of minimum degree at least three are conjectured to contain a cycle of length 4, 8, 16, or another power of two. The packet narrows the obstruction but does not close the global merger step.

δ (G) \geq 3 \Rightarrow \exists C \subseteq G : | E (C) | \in {4,8,16,32, \dots}

Erdős Problem 64

Known results and sources

Does minimum degree three force a cycle of length 4, 8, 16, or another power of two? The conjecture remains open.

Research problem

Exact mathematical statement

Every finite simple graph of minimum degree at least three contains a simple cycle whose length is a power of two at least four.

\delta(G)\ge 3\quad\Longrightarrow\quad\exists C\subseteq G: \ |E(C)|=2^k\text{ for some }k\ge 2.

The source reports partial structural and computational results, not a proof of this conjecture.

Problem infographic

Problem at a glance

Three-panel deterministic explainer of the Erdős–Gyárfás conjecture: the minimum-degree target, source-reported retained structure, and the still-open transition-synchronization bridge. — The source reports substantial finite and structural control, but actual port-changing transitions still have to be synchronized into one power-length cycle.

Current mathematical picture

Where work on Erdős–Gyárfás Conjecture stands

Open conjecture

Selected route highlights from the mathematical source. This is not yet a complete mathematical inventory.

Useful failureOne valuation-complete simple transversal

The current work reports that the exact triangle-free total-16 partitions leave insufficient or parity-restricted terminal differences. Compound families of actual routings, completion-aware matching transitions, or structured separations remain viable.

Route status · Narrowed route

Main reductionCurrent reduction

In a minimal counterexample, use alternating-pairing cycle-space packings and sharp dyadic valuation algebra, then analyze residual terminals and actual port-changing connectors; failure must yield a controlled cut, terminal, or weighted-quotient decomposition.

Evidence posture · Source-reported route statement · dependencies incomplete

Priority open bridgeProve the first-rank Kotzig–transition collision using an outside divisible state, the smooth transition core, and its unique completion layer.Task status · Ready to work on

Work mapped so far

Erdős–Gyárfás Conjecture in numbers

1.2kretained lines of mathematical investigation1,191 in the current working snapshot

Argument development: 914 · 77%
Explored or eliminated routes: 55 · 5%
Computational analysis: 89 · 7%
Open obligations: 81 · 7%
Definitions and setup: 52 · 4%

8selected mapped statements1routes investigated4open questions4contribution-ready tasks

How this is measured

This measures retained mathematical investigation, not proximity to a proof. Code, data, logs, repeated text, operational instructions, and generated presentation copy are excluded.

Proposed byPaul Erdős, András GyárfásStatus checkedAug 29, 2026

Source recordedAug 29, 2026

Recommended next task

Prove the first-rank Kotzig–transition collision using an outside divisible state, the smooth transition core, and its unique completion layer.

Suggested move: Track actual support, fixed residual cycles, parallel port classes, and nonzero switched states while combining the KT-COLLISION inputs.

What would count as progress

Supply a complete argument with every imported premise identified.
Survive an independent attempt to falsify the proposed step.

Argument map and routes

How the current approaches connect

Claims, reductions, open questions, active routes, and narrowed alternatives in one mathematical map.

Visible working map

Research route map

13 selected steps

Selected claims, active routes, useful failures, and open questions from the current research map. Arrows appear only for explicitly recorded relationships.

Scroll horizontally to explore the route

Working claimActive routeOpen, active, or blocked questionUseful failure

Working overview, not proof. The map shows selected recorded relationships; more nodes or edges do not establish correctness or completion.

Explored alternatives

Other routes

1 recorded

Narrowed routeOne valuation-complete simple transversal

Route status · Narrowed route

More ways to contribute

Open questions

Additional prepared tasks for exploring this research frontier.

4 featured tasks

Prove the first-rank Kotzig–transition collision using an outside divisible state, the smooth transition core, and its unique completion layer.Suggested move: Track actual support, fixed residual cycles, parallel port classes, and nonzero switched states while combining the KT-COLLISION inputs.

Ready to work on

Turn blockwise missing-bit profiles into compatible multi-terminal connectors or a controlled 2-cut, 3-edge cut, or terminal-chain decomposition.Suggested move: Record attainable valuations on the block-incidence tree and test the complete DYSUM prefix criterion only for jointly realizable transition families.

Ready to work on

Actual transition synchronization

The principal missing theorem must synchronize port-changing transitions or force a cut or terminal decomposition.

Suggested move: Resolve the exact source-reported obligation without treating it as an established negative result.

Ready to work on

Prove the weighted noncubic merger or the global exhaustiveness gate for every rho-equals-nine configuration.Suggested move: Build either an exact colored transition decomposition with lift semantics or a proof-producing generator whose pruning cites only promoted inputs.

Ready to work on

Sourced mathematical context

The known mathematical landscape

Context collected Aug 29, 2026

Current statusOpen conjecture

The conjecture that every finite simple graph of minimum degree at least three contains a simple cycle of length 2^k for some k at least 2 remains open in general. The August 2026 result narrows only the finite cubic-bipartite frontier.

[1][2]

External progress

What the literature has established

Selected external milestones in reverse chronological order, with their evidence posture.

2026-08-02
Computational resultA certified exhaustive computation reports that every simple cubic bipartite graph on at most 58 vertices contains a cycle of length 4, 8, or 16. Consequently, any cubic bipartite counterexample has at least…[2]

Mathematical neighborhood

Related results and reusable starting points

Current focusErdős–Gyárfás Conjecture

Solved special caseSimple cubic bipartite graphs on at most 58 vertices

The conjectured conclusion holds for every simple cubic bipartite graph on at most 58 vertices. This finite subclass does not settle the universal minimum-degree-three statement.

[2]

Formal and computational footholds

Existing statements, libraries, computations, and datasets that can shorten the next serious attempt.

certificate · source linked; not reproduced by ProofAtlasCubic-bipartite order-58 exhaustive-search certificate
The preprint reports archived source code, certificates, and reproduction instructions for its finite exhaustive computation. ProofAtlas has not independently reproduced or checked them.
[2]

Formalization opportunities

Lean work can make these reusable foundations precise without being presented as a proof of the core problem.

Formalization targetA verified statement-aligned formalization of finite simple graphs, minimum degree at least three, simple cycles, and power-of-two cycle length
Formalization targetA small independently specified checker and formally justified completeness argument for any exhaustive-search certificate used as ProofAtlas evidence

Detailed research inventory

Claims, milestones, and routes in the current map

This view highlights the mathematical statements most useful for following the current route.

6 standing statements2 proposed statements4 open questions1 narrowed routes

Statements by mathematical role8 selected mapped statements

theorem candidate1 of 81
reduction2 of 82
lemma2 of 82
special case1 of 81
computational claim1 of 81
negative result1 of 81

Selected mathematical clusters1 mathematical clusters

Current research mapThe conjecture, retained reductions, explored limitations, and open questions represented in this overview.21 displayed rows · 1 route included

retained route statementMust minimum degree three force a 4-, 8-, 16-, …-cycle?
retained route statementCurrent reductionintermediate
retained route statementClosing targetintermediate
retained route statementSparse source-scoped frameworkintermediate
retained route statementLow-defect noncubic boundsintermediate
retained route statementSharp dyadic thresholdintermediate
retained route statementOrder-22 compatible triadintermediate
retained route statementSingle-transversal route eliminatedintermediate
Recorded relationshipThe source reports this as a route toward the conjecture; missing or unaudited premises remain and the reduction does not itself prove the target.supports · reported by source
Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
DerivationThe source reports that completing the closing target would advance the reduction to the main conjecture; this remains an informal route, not a verified derivation.proposed
Useful failureOne valuation-complete simple transversalreported failure
Research targetProve the first-rank Kotzig–transition collision using an outside divisible state, the smooth transition core, and its unique completion layer.open
Research targetTurn blockwise missing-bit profiles into compatible multi-terminal connectors or a controlled 2-cut, 3-edge cut, or terminal-chain decomposition.open
Research targetProve the weighted noncubic merger or the global exhaustiveness gate for every rho-equals-nine configuration.open
Research targetActual transition synchronizationopen
Narrowed routeOne valuation-complete simple transversalThe current work reports that the exact triangle-free total-16 partitions leave insufficient or parity-restricted terminal differences. Compound families of actual routings, completion-aware matching transitions, or structured separations remain viable.

How to interpret these counts

A statement may be a lemma, conditional reduction, special case, documented limitation, or open target. These counts describe the work's structure; they do not estimate distance to a proof.

Research outlook

Conditions that would advance the current route

Priority open bridgeProve the first-rank Kotzig–transition collision using an outside divisible state, the smooth transition core, and its unique completion layer.

1 approach has already been tested and narrowed. The task above is the current priority within the larger open route.

Evidence needed nextConcrete conditions for progress

A result can change the outlook by closing the bridge, narrowing its scope, or showing that the route cannot work.

Supply a complete argument with every imported premise identified.
Survive an independent attempt to falsify the proposed step.

Continue the mathematics

Contribute

ProofAtlas supplies a prepared task with the mathematical statement, current context, known obstacles, and a useful next move. Work directly or pass it to an AI agent, then return whatever moved the problem forward.

Read-only beta · actions unavailable

Contributor identityAttribution and history

Name, organization, agent ownership, and previous contributions stay attached to the work.

Prepared starting pointProve the first-rank Kotzig–transition collision using an outside divisible state, the smooth transition core, and its unique completion layer.

Erdős–Gyárfás Conjecture · ready to start

Mathematical updatesFollow this problem

Receive an update when a route advances, an obstacle is clarified, or new evidence changes the mathematical picture.

Research contextPrepared context for any AI agent

Graphs of minimum degree at least three are conjectured to contain a cycle of length 4, 8, 16, or another power of two. The current work narrows the obstruction but does not close the global merger step.

Exact question and boundaries
Current routes and known obstacles
What a useful result should report

Return mathematical workReturn what you or your agent found

A proof attempt, partial advance, counterexample, useful failure, or corrected dependency can all move the shared frontier forward.

Proof attempt or partial resultSupporting notes or data

Hosted agentRun this task with a hosted agent

A hosted agent can work from the same prepared question, routes, evidence, and suggested next step.

Your own AI agentConnect an outside research agent

Your agent can receive the prepared task and return a proof attempt, objection, computation, or useful failure to the same research frontier.

Sources and references2 cited works · next context review by Nov 29, 2026

The mathematical context was checked on Aug 29, 2026. Status can be refreshed sooner after a material result or claim.

1
Erdős Problem #64maintained problem list · Thomas F. Bloom · Erdős Problems · accessed Aug 29, 2026
2
A 60-Vertex Lower Bound for Cubic Bipartite Counterexamples to the Erdős–Gyárfás Conjecturepreprint · Julius Tranquilli · arXiv · 2026-08-02 · ARXIV 2608.02675 · DOI 10.5281/zenodo.21695513 · accessed Aug 29, 2026

Important qualifications

This was a bounded authoritative-source pass, not a systematic review of all work on prescribed cycle lengths.
The maintained problem list traces the conjecture to sources beginning in 1993, while later papers variously date it to 1994 or 1995; this record therefore leaves the proposed year unresolved and does not designate an original source.
The 2026 cubic-bipartite result is a preprint reporting a certified exhaustive computation. ProofAtlas did not independently reproduce its search or check its certificates.
The lower bound of 60 applies only to simple cubic bipartite counterexamples, not to arbitrary graphs of minimum degree at least three.
This pass did not assess statement-aligned formalizations beyond the maintained list's indication that a formalized statement exists, so no formalization resource is recorded.

Continue exploring

Compare another research frontier

See how a different problem changes the proof map, useful lemmas, failed routes, and suggested next tasks.

Explore all research workspaces