IsClawFree
def
A simple graph G is claw-free if it does not contain the complete bipartite graph K_{1,3} as an induced subgraph.
Statement
def IsClawFree {V : Type*} (G : SimpleGraph V) : Prop
- Defined in
- arXiv:2610.20129 Sec. 1.1
- Verified
- 25 Oct 2026
- Axioms
- none listed
- Used by 11
- k4_claw_diamond_free_has_no_induced_k4_subdivisionEvery simple graph containing neither an induced K4, an induced claw, nor an induced diamond contains no induced subdivision of K4.
- not_p7_claw_free_dominating_pair_of_no_holeThe statement
p7_claw_free_dominating_pair_of_no_holeis false: The statement is FALSE. A concrete counterexample is the net graph (a… - odd_cycle_is_claw_freeFor every integer n ≥ 1, the odd cycle graph C_{2n+1} is claw-free.
- not_is_pk_free_claw_free_hole_dominatingThe statement
is_pk_free_claw_free_hole_dominatingis false: The statement is false as written: it allows k = 4 and m = 3 (since k - 1 =… - subdivided_k33_line_graph_isk4_diamond_free_four_chromaticLet H be the graph obtained from K3,3 by subdividing one edge exactly once, and let G be its line graph. Then G has no induced subdivision…
- claw_free_adj_of_neighborsIn any claw-free graph G, if a vertex x is adjacent to three pairwise distinct vertices u, v, and w, and w is adjacent to neither u nor v,…
- is_claw_free_triple_neighborsIn any claw-free graph, among any three distinct neighbors of a vertex, at least two are adjacent.
- op_1355_claw_free_of_weighted_boundIf a finite simple graph G on a finite type V with decidable equality satisfies the weighted hard-core closed-neighborhood variance bound…
- is_claw_free_topEvery complete graph is claw-free.
- op_1355_clique_components_is_claw_freeEvery finite simple graph G on a finite type V with decidable equality whose connected components are all cliques is claw-free.
- subdivided_k33_line_graph_no_k4_claw_diamondThe line graph of the once-subdivided K3,3 has no induced K4, claw, or diamond.
Read back from the Lean
For a type V and a simple graph G on V, IsClawFree G is defined to hold if and only if the complete bipartite graph $K_{1, 3}$ with parts of size 1 and 3 (specifically, with vertex type Fin 1 ⊕ Fin 3) is not an induced subgraph of G (i.e., ¬ SimpleGraph.IsIndContained (completeBipartiteGraph (Fin 1) (Fin 3)) G).
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 is claw-free if it does not contain K_{1,3} as an induced subgraph. -/ def IsClawFree {V : Type*} (G : SimpleGraph V) : Prop := ¬ SimpleGraph.IsIndContained (completeBipartiteGraph (Fin 1) (Fin 3)) G