AFTD Auto-Formalizing Theoretical Domains

cnf_incidence_treewidth_le_card

theoremverified

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

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|.

  1. 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.

    line 3

      unfold cnf_incidence_treewidth graph_treewidth
  2. The 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.

    lines 4–6

    uses has_tree_decomposition_single_bag

      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
  3. 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.

    line 7

    uses le_trans, Nat.sInf_le, Nat.sub_le

      exact 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).

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

/-- 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 _ _)
See it in the graphDiscuss this resultChallenge it