Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Exact finite treewidth recognition and reconstruction with at most n+1 bags

Proved
StableMSR.Recovery.DecompositionSearch.finite_decomposition_search

by lreyzin · Nov 14, 2026 · Mathlib 0df444a (Lean v4.33.1)

For every finite simple graph GGG on nnn vertices and every nonnegative integer www, the depth-bounded tight-block recurrence recognizes precisely the graphs of treewidth at most www:

recognizes⁡(G,w)  ⟺  tw⁡(G)≤w.\operatorname{recognizes}(G,w)\iff\operatorname{tw}(G)\le w.recognizes(G,w)⟺tw(G)≤w.

Whenever it succeeds, there is a finite tree decomposition in the canonical path-based definition, all of whose bags have at most w+1w+1w+1 vertices and whose tree has at most n+1n+1n+1 nodes. The empty graph is represented by a single empty bag. Recognition runs each initial component with empty boundary and depth nnn; each transition selects a bounded bag introducing a vertex and recursively tests the remaining connected components with their exact external boundaries. This theorem proves both semantic completeness and output reconstruction, including running intersection and the linear bag bound. It asserts neither a polynomial instruction count nor an implementation in the charged clustering-recovery interpreter.

Preamble
import Definitions.Def_StableMSR_DecompositionSearch_Recurrence
import Definitions.Def_RobertsonSeymour1986_GM5_TreewidthLE
open StableMSR.Recovery.DecompositionSearch RobertsonSeymour1986.GM5
Formal statement
theorem StableMSR.Recovery.DecompositionSearch.finite_decomposition_search {V : Type} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (w : ℕ) :
    (recognizes G w ↔ TreewidthLE G w) ∧
    (recognizes G w →
      ∃ (T : Type) (ft : Fintype T) (tree : SimpleGraph T) (bags : T → Finset V),
        IsTreeDecomposition G tree bags ∧ (∀ t, (bags t).card ≤ w+1) ∧
        @Fintype.card T ft ≤ Fintype.card V + 1) := by sorry
Source
Finite tight-boundary decomposition search and reconstruction supporting the Prove2Me mission Exact Sum-of-Radii Clustering under Any Constant Stability; canonical treewidth definition and previously proved tight-block progress lemma.

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