AFTD Auto-Formalizing Theoretical Domains

is_claw_packing

def

For a simple graph G on type V and a finite set of finite vertex subsets P : Finset (Finset V), is_claw_packing G P asserts that every s in P satisfies is_induced_claw G s and the elements of P are pairwise disjoint.

Statement

def is_claw_packing {V : Type*} (G : SimpleGraph V) (P : Finset (Finset V)) : Prop
Defined in
arXiv:2511.19585
Verified
01 Nov 2026
Axioms
none listed
Built on 1
  • is_induced_clawFor a simple graph G on type V and a finite subset of vertices s : Finset V, is_induced_claw G s asserts that the induced subgraph of G on…
Used by 1
  • max_claw_packingFor a simple graph G on a finite type V, max_claw_packing G is defined as the supremum of Finset.card P over all P : Finset (Finset V) in…

Read back from the Lean

For a simple graph G on vertex type V and a finite set P of finite subsets of V, is_claw_packing G P asserts that: 1. For every s ∈ P, the induced subgraph G.induce (s : Set V) is isomorphic (via a simple graph isomorphism) to the complete bipartite graph completeBipartiteGraph (Fin 1) (Fin 3) (i.e., the claw graph $K_{1,3}$); and 2. The collection P is pairwise disjoint with respect to the identity (i.e., for all s₁, s₂ ∈ P, if s₁ ≠ s₂, then Disjoint s₁ s₂).

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 collection of pairwise vertex-disjoint induced claws in a graph. -/
def is_claw_packing {V : Type*} (G : SimpleGraph V) (P : Finset (Finset V)) : Prop := (∀ s ∈ P, is_induced_claw G s) ∧ (P : Set (Finset V)).PairwiseDisjoint id
See it in the graphDiscuss this resultChallenge it