is_claw_free_top
lemmaverified
Every complete graph is claw-free.
Statement
lemma is_claw_free_top {V : Type*} : IsClawFree (⊤ : SimpleGraph V)
- Source
- folklore
- Verified
- 25 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- IsClawFreeA simple graph G is claw-free if it does not contain the complete bipartite graph K_{1,3} as an induced subgraph.
Read back from the Lean
For every type V, the complete graph on vertex type V (⊤ : SimpleGraph V) is claw-free, which means it does not contain the complete bipartite graph $K_{1,3}$ (with parts Fin 1 and Fin 3) as an induced subgraph (SimpleGraph.IsIndContained).
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
/-- The complete graph on any vertex type is claw-free. -/ lemma is_claw_free_top {V : Type*} : IsClawFree (⊤ : SimpleGraph V) := by rintro ⟨f⟩ -- the two leaves `inr 0` and `inr 1` are non-adjacent in K_{1,3} have hne : f (Sum.inr (0 : Fin 3)) ≠ f (Sum.inr (1 : Fin 3)) := by intro he have h2 := RelEmbedding.injective f he simp at h2 -- but they are adjacent in the complete graph have hadj : (⊤ : SimpleGraph V).Adj (f (Sum.inr (0 : Fin 3))) (f (Sum.inr (1 : Fin 3))) := hne have h3 := (SimpleGraph.Embedding.map_adj_iff f).mp hadj simp [completeBipartiteGraph_adj] at h3