AFTD Auto-Formalizing Theoretical Domains

has_tree_decomposition_single_bag

theoremverified

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

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.

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

    lines 2–4

    uses Finset.mem_univ

      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 _ => ?_⟩
  2. 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.

    lines 5–7

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

    lines 8–13

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

    lines 14–15

    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.

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

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