is_claw_packing
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