Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Finite graphs are α\alphaα-WQO under minors for every ordinal α\alphaα

Open
TenChallenges.challenge_06_all_graphs

by Davide · Nov 17, 2026 · Mathlib 0df444a (Lean v4.33.1)

bqograph-minorsopen-problemten-challengeswqo

The better-quasi-ordering conjecture for graph minors, for all finite graphs. For every ordinal α\alphaα, the class of finite simple graphs is α\alphaα-well-quasi-ordered by the minor relation ⪯\preceq⪯:

∀ α∈Ord:(Vα∗(Gfin),≤∗) is well-quasi-ordered.\forall\,\alpha\in\mathrm{Ord}:\quad (V^*_\alpha(\mathcal G_{\mathrm{fin}}),\le^*)\ \text{is well-quasi-ordered}.∀α∈Ord:(Vα∗​(Gfin​),≤∗) is well-quasi-ordered.

This is the odd-rung half of the Challenge 6 goal, WQO(2α+1)\mathrm{WQO}(2\alpha+1)WQO(2α+1) for every α\alphaα. The case α=0\alpha=0α=0 is the Robertson-Seymour Graph Minor Theorem; every case α≥1\alpha\ge1α≥1 is open. Since better-quasi-ordering is α\alphaα-WQO for every α\alphaα, this is equivalent to the folklore conjecture that finite graphs are BQO under minors. The planar half of the goal follows from this statement because α\alphaα-WQO passes to subclasses.

Preamble
import Definitions.Def_TenChallenges_AlphaWQO
Formal statement
namespace TenChallenges
theorem challenge_06_all_graphs : ∀ α : Ordinal, IsAlphaWQO FiniteGraph.MinorLE α := by sorry
end TenChallenges
Source
Ten Challenges 06 mission statement (folklore BQO conjecture for graph minors; see Georgakopoulos 2025, https://arxiv.org/abs/2510.19285). Odd rungs r = 2·α + 1 of TenChallenges.statement_06.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me