Exact finite treewidth recognition and reconstruction with at most n+1 bags
ProvedStableMSR.Recovery.DecompositionSearch.finite_decomposition_searchFor every finite simple graph on vertices and every nonnegative integer , the depth-bounded tight-block recurrence recognizes precisely the graphs of treewidth at most :
Whenever it succeeds, there is a finite tree decomposition in the canonical path-based definition, all of whose bags have at most vertices and whose tree has at most nodes. The empty graph is represented by a single empty bag. Recognition runs each initial component with empty boundary and depth ; 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.
import Definitions.Def_StableMSR_DecompositionSearch_Recurrence import Definitions.Def_RobertsonSeymour1986_GM5_TreewidthLE open StableMSR.Recovery.DecompositionSearch RobertsonSeymour1986.GM5
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