cnf_incidence_treewidth_le_card
Universal upper bound: the incidence treewidth of any CNF formula F is at most |vars(F)| + |F|.
Statement
theorem cnf_incidence_treewidth_le_card (F : Finset (Finset (CnfLit ℕ))) : cnf_incidence_treewidth F ≤ (cnf_vars F).card + F.card- Source
- step towards resolution_fpt_incidence_treewidth
- Verified
- 23 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 7
- cnf_incidence_treewidthThe incidence treewidth tw*(F) of a CNF formula F: the treewidth of its incidence graph.
- cnf_varsThe set var(F) of variables occurring in a CNF formula F, given as a finite set of clauses, each a finite set of literals.
- has_tree_decomposition_single_bagSanity check: every finite graph has a tree decomposition of width at most (number of vertices - 1), the one-node tree whose bag is every…
- CnfLitA CNF literal over a variable type V is either a positive variable or a negated variable.
- cnf_incidence_graphThe incidence graph G*(F) of a CNF formula F: the bipartite graph whose vertices are the variables of F and the clauses of F, a variable x…
- 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…
- graph_treewidthThe treewidth of a graph: the least w such that it has a tree decomposition of width at most w.
- Used by 1
- cnf_incidence_treewidth_emptyThe incidence treewidth of the empty formula is 0.
The proof, explained
The incidence treewidth of a CNF formula F is defined as the treewidth of its incidence graph, which is the infimum of the widths of all its valid tree decompositions. Every finite graph admits a trivial single-bag tree decomposition containing all vertices, whose width is the total number of vertices minus one. The vertex set of the incidence graph is the disjoint union of the variable set and the clause set of F, giving |vars(F)| + |F| vertices in total. This single-bag decomposition therefore witnesses that the treewidth is at most (|vars(F)| + |F|) - 1 ≤ |vars(F)| + |F|.
The goal reduces to showing that the infimum of valid tree decomposition widths for the incidence graph of F is at most |vars(F)| + |F|.
Unfolding cnf_incidence_treewidth and graph_treewidth expresses the treewidth as the infimum of all w ∈ ℕ for which the incidence graph has a tree decomposition of width at most w.
unfold cnf_incidence_treewidth graph_treewidthThe incidence graph of F has a tree decomposition of width at most (|vars(F)| + |F|) - 1.
Any finite graph admits a trivial single-bag tree decomposition whose bag contains every vertex, having width at most |V| - 1 (has_tree_decomposition_single_bag). The vertex set of the incidence graph is the disjoint sum of the variables vars(F) and the clauses F, so its cardinality is |vars(F)| + |F|, as verified by simp. Rewriting this cardinality into the single-bag decomposition yields a decomposition of width (|vars(F)| + |F|) - 1.
uses
has_tree_decomposition_single_baghave h := has_tree_decomposition_single_bag (cnf_incidence_graph F) have hcard : Fintype.card (↥(cnf_vars F) ⊕ ↥F) = (cnf_vars F).card + F.card := by simp rw [hcard] at h
The incidence treewidth of F is at most |vars(F)| + |F|.
Since (|vars(F)| + |F|) - 1 is the width of a valid tree decomposition, the infimum over all valid widths is at most this value (Nat.sInf_le). Because n - 1 ≤ n for every natural number (Nat.sub_le), transitivity of inequality (le_trans) establishes the bound.
uses
le_trans,Nat.sInf_le,Nat.sub_leexact le_trans (Nat.sInf_le h) (Nat.sub_le _ _)
has_tree_decomposition_single_bag- Any finite graph on vertex type α has a tree decomposition consisting of a single bag containing all vertices, with width at most |α| - 1.
le_trans- Inequality is transitive: if a ≤ b and b ≤ c, then a ≤ c.
Nat.sInf_le- If a natural number m belongs to a set s ⊆ ℕ, then the infimum of s is at most m.
Nat.sub_le- For any natural numbers n and m, subtracting m from n yields at most n (n - m ≤ n).
- In Lean, subtraction on natural numbers truncates at zero (so 0 - 1 = 0), ensuring that Nat.sub_le holds unconditionally, even if the formula has no variables and no clauses.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. 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.
/-- The incidence treewidth of any CNF formula is bounded above by the sum of the number of variables and the number of clauses. -/theorem cnf_incidence_treewidth_le_card (F : Finset (Finset (CnfLit ℕ))) : cnf_incidence_treewidth F ≤ (cnf_vars F).card + F.card := by unfold cnf_incidence_treewidth graph_treewidth have h := has_tree_decomposition_single_bag (cnf_incidence_graph F) have hcard : Fintype.card (↥(cnf_vars F) ⊕ ↥F) = (cnf_vars F).card + F.card := by simp rw [hcard] at h exact le_trans (Nat.sInf_le h) (Nat.sub_le _ _)