has_tree_decomposition_single_bag
Sanity check: every finite graph has a tree decomposition of width at most (number of vertices - 1), the one-node tree whose bag is every vertex; so treewidth is well defined on finite graphs.
Statement
theorem has_tree_decomposition_single_bag {α : Type*} [Fintype α] (G : SimpleGraph α) : has_tree_decomposition_of_width_le G (Fintype.card α - 1)
- Source
- sanity check of has_tree_decomposition_of_width_le / graph_treewidth (arXiv:2610.02047 Sec. 3.2): the one-bag decomposition, a textbook observation that treewidth is well defined
- Verified
- 06 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- has_tree_decomposition_of_width_leA graph G has a tree decomposition of width at most w: a finite tree T and bags chi(t), subsets of the vertices of G, such that every…
- Used by 1
- cnf_incidence_treewidth_le_cardUniversal upper bound: the incidence treewidth of any CNF formula F is at most |vars(F)| + |F|.
The proof, explained
To show every finite graph has a tree decomposition of width at most |V| - 1, we construct the trivial decomposition having a single tree node whose bag contains all vertices of the graph. Because the tree has only one vertex, it is trivially a tree, all edges and vertices are covered in that single bag, and the induced subgraph for each vertex is connected. The width condition then reduces to checking that |V| ≤ (|V| - 1) + 1, which holds by natural number arithmetic.
The graph G admits a candidate tree decomposition with a single bag containing all vertices, which immediately satisfies vertex and edge coverage.
We exhibit a tree decomposition with 1 node (the type Fin 1), the empty graph ⊥ on Fin 1, and the bag function mapping the unique node 0 to Finset.univ. Since Finset.univ contains all vertices of α by Finset.mem_univ, every vertex v is contained in bag 0, and for every edge between u and v, both endpoints are contained in bag 0.
uses
Finset.mem_univclassical refine ⟨1, ⊥, fun _ => Finset.univ, ?_, fun v => ⟨0, Finset.mem_univ v⟩, fun u v _ => ⟨0, Finset.mem_univ u, Finset.mem_univ v⟩, ?_, fun _ => ?_⟩
The one-vertex graph ⊥ on Fin 1 is a tree.
A tree is defined as an acyclic and connected graph. The empty graph ⊥ is acyclic by SimpleGraph.isAcyclic_bot. To show it is connected, we check that any two vertices u, v : Fin 1 can reach each other: since Fin 1 has at most one element, u = v by Subsingleton.elim, and every vertex can reach itself by SimpleGraph.Reachable.refl.
uses
SimpleGraph.isAcyclic_bot,Subsingleton.elim,SimpleGraph.Reachable.refl· refine ⟨⟨fun u v => ?_⟩, SimpleGraph.isAcyclic_bot⟩ obtain rfl := Subsingleton.elim u v exact SimpleGraph.Reachable.refl u
For every vertex v in G, the induced subgraph on the bags containing v is connected.
Given any vertex v, the subset of nodes whose bag contains v is nonempty because node 0 contains v by Finset.mem_univ. Any two nodes u, w in this induced subgraph must be equal by Subsingleton.elim since the underlying type is Fin 1, and u can reach itself by SimpleGraph.Reachable.refl.
uses
Finset.mem_univ,Subsingleton.elim,SimpleGraph.Reachable.refl· intro v haveI : Nonempty ({t | v ∈ (Finset.univ : Finset α)} : Set (Fin 1)) := ⟨⟨0, Finset.mem_univ v⟩⟩ refine ⟨fun u w => ?_⟩ obtain rfl := Subsingleton.elim u w exact SimpleGraph.Reachable.refl u
The unique bag has size at most (card(α) - 1) + 1. automation
Rewriting the cardinality of Finset.univ with Finset.card_univ reduces the goal to Fintype.card α ≤ (Fintype.card α - 1) + 1. The decision procedure omega closes this by natural number linear arithmetic.
uses
Finset.card_univ· simp only [Finset.card_univ] omega
Finset.mem_univ- Every element of a finite type belongs to the universal finset of that type.
SimpleGraph.isAcyclic_bot- The empty graph on any vertex type contains no cycles.
Subsingleton.elim- Any two elements of a subsingleton type are equal.
SimpleGraph.Reachable.refl- In any graph, every vertex is reachable from itself.
Finset.card_univ- The cardinality of the universal finset of a finite type equals the cardinality of the type.
- Due to truncated subtraction on natural numbers (0 - 1 = 0), the statement also holds when α is empty, with width 0 and bag cardinality 0 ≤ 0 + 1.
Written by a model (gemini-3.8-flash) from the Lean source alone (no goal states were available). Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
theorem has_tree_decomposition_single_bag {α : Type*} [Fintype α] (G : SimpleGraph α) : has_tree_decomposition_of_width_le G (Fintype.card α - 1) := by classical refine ⟨1, ⊥, fun _ => Finset.univ, ?_, fun v => ⟨0, Finset.mem_univ v⟩, fun u v _ => ⟨0, Finset.mem_univ u, Finset.mem_univ v⟩, ?_, fun _ => ?_⟩ · refine ⟨⟨fun u v => ?_⟩, SimpleGraph.isAcyclic_bot⟩ obtain rfl := Subsingleton.elim u v exact SimpleGraph.Reachable.refl u · intro v haveI : Nonempty ({t | v ∈ (Finset.univ : Finset α)} : Set (Fin 1)) := ⟨⟨0, Finset.mem_univ v⟩⟩ refine ⟨fun u w => ?_⟩ obtain rfl := Subsingleton.elim u w exact SimpleGraph.Reachable.refl u · simp only [Finset.card_univ] omega