AFTD Auto-Formalizing Theoretical Domains

simple_graph_has_star_decomposition_bot

theoremverified

For any natural number q, the empty graph on one vertex has a star decomposition into copies of K_{1,q}.

Statement

theorem simple_graph_has_star_decomposition_bot (q : ℕ) :
    simple_graph_has_star_decomposition (⊥ : SimpleGraph (Fin 1)) q
Source
folklore
Verified
22 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1

Read back from the Lean

For every natural number q, the empty simple graph on the 1-element vertex type Fin 1 has a q-star decomposition: there exists a collection P of sets of unordered pairs from Fin 1 (edges) such that the union ⋃₀ P equals the edge set of the empty graph on Fin 1, the sets in P are pairwise disjoint, every set s in P has cardinality q (in the sense of Set.ncard), and for every set s in P, there exists a vertex v : Fin 1 such that v is incident to every edge in s.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The theorem is proved by taking the empty set ∅ as the collection of stars. Because the empty graph on one vertex has no edges, the union condition is trivial, and all remaining conditions—pairwise disjointness, cardinality q, and being a star graph—hold vacuously for elements of the empty set.

  1. The empty family of subgraphs is a valid star decomposition of the empty graph ⊥ into copies of K_{1,q}.

    We supply the empty set ∅ as the witness for the existential quantification in the definition of star decomposition. The goal reduces to showing that the union of edges in ∅ equals the edge set of ⊥, that ∅ is pairwise disjoint, that every subgraph in ∅ has cardinality q, and that every subgraph in ∅ is a star. Because the empty graph ⊥ has no edges and ∅ has no elements, all of these conditions hold vacuously; the simplifier verifies them after unfolding `Set.PairwiseDisjoint`.

    line 4

    uses Set.PairwiseDisjoint

      exact ⟨∅, by simp [Set.PairwiseDisjoint]⟩
Set.PairwiseDisjoint
A property asserting that a family of sets indexed by a set is pairwise disjoint, meaning that distinct indices map to disjoint sets.

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

/-- Sanity lemma: the empty graph on one vertex vacuously has a star decomposition into copies of K_{1,q}. -/theorem simple_graph_has_star_decomposition_bot (q : ℕ) :    simple_graph_has_star_decomposition (⊥ : SimpleGraph (Fin 1)) q := by  exact ⟨∅, by simp [Set.PairwiseDisjoint]⟩
See it in the graphDiscuss this resultChallenge it