simple_graph_has_star_decomposition
A 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 disjoint family of subsets of size q such that each subset of edges shares a common vertex.
Statement
def simple_graph_has_star_decomposition {V : Type*} (G : SimpleGraph V) (q : ℕ) : Prop
- Related work
- arXiv:2610.07034 Corollary 1.2
- Verified
- 22 Oct 2026
- Axioms
- none listed
- Used by 1
- simple_graph_has_star_decomposition_botFor any natural number q, the empty graph on one vertex has a star decomposition into copies of K_{1,q}.
Read back from the Lean
For a type V, a simple graph G on V, and a natural number q, simple_graph_has_star_decomposition G q asserts that there exists a set P of subsets of Sym2 V such that:
1. The union of the sets in P is equal to the edge set of G (⋃₀ P = G.edgeSet),
2. The sets in P are pairwise disjoint (Set.PairwiseDisjoint P id),
3. Every set s ∈ P has s.ncard = q (its cardinality is q), and
4. For every set s ∈ P, there exists a vertex v : V such that every edge e ∈ s contains v (i.e., v is an endpoint of e).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- A simple graph G admits a star decomposition into copies of K_{1,q} if its edge set can be partitioned into sets of size q, each of which forms a star graph. -/ def simple_graph_has_star_decomposition {V : Type*} (G : SimpleGraph V) (q : ℕ) : Prop := ∃ P : Set (Set (Sym2 V)), ⋃₀ P = G.edgeSet ∧ Set.PairwiseDisjoint P id ∧ (∀ s ∈ P, s.ncard = q) ∧ ∀ s ∈ P, ∃ v : V, ∀ e ∈ s, v ∈ e