simple_graph_has_star_decomposition_bot
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
- simple_graph_has_star_decompositionA simple graph G has a star decomposition into copies of the star graph K_{1,q} if its edge set can be partitioned into a pairwise…
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.
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`.
uses
Set.PairwiseDisjointexact ⟨∅, 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
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.
/-- 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]⟩