Graph Minors IV: graphs of bounded tree-width are well-quasi-ordered by minors
OpenTenChallenges.bounded_treewidth_wqoGraphs of bounded tree-width are well-quasi-ordered by minors. Fix an integer . For every infinite sequence of finite simple graphs, each of tree-width at most , there are indices such that is a minor of :
This is the main theorem of Graph Minors IV, proved by Robertson and Seymour with a Nash-Williams-style minimal bad sequence argument on tree-decompositions. Combined with the Excluded Grid Theorem of Graph Minors V, it gives that every class excluding a fixed planar minor is well-quasi-ordered, and in particular that finite planar graphs are.
Formalization Note Tree-width at most is TreewidthLE G w from Graph Minors V (a tree-decomposition with bags of size at most ); so the hypothesis is tree-width , matching the paper's "tree-width " with . Graphs are FiniteGraph (simple graphs on Fin n), and the minor relation is the branch-set model FiniteGraph.MinorLE.
import Definitions.Def_TenChallenges_AlphaWQO import Definitions.Def_RobertsonSeymour1986_GM5_TreewidthLE
namespace TenChallenges
theorem bounded_treewidth_wqo (w : ℕ) (f : ℕ → FiniteGraph)
(hf : ∀ n, RobertsonSeymour1986.GM5.TreewidthLE (f n).2 w) :
∃ i j, i < j ∧ FiniteGraph.MinorLE (f i) (f j) := by sorry
end TenChallenges