AFTD Auto-Formalizing Theoretical Domains

simple_graph_has_star_decomposition

deforiginal

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

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