AFTD Auto-Formalizing Theoretical Domains

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