op_1355_clique_components_is_claw_free
Every finite simple graph G on a finite type V with decidable equality whose connected components are all cliques is claw-free.
Statement
theorem op_1355_clique_components_is_claw_free {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (hclique : ∀ c : G.ConnectedComponent, G.IsClique c.supp) : IsClawFree G
- Source
- knowledgebase
- Verified
- 10 Nov 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
Let $V$ be a finite type with decidable equality, and let $G$ be a simple graph on $V$. Suppose that for every connected component $c$ of $G$, the vertex set of $c$ (c.supp) is a clique in $G$. Then $G$ is claw-free, meaning that $G$ does not contain the complete bipartite graph $K_{1, 3}$ (completeBipartiteGraph (Fin 1) (Fin 3)) as an induced subgraph.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The proof proceeds by contradiction: suppose $G$ contains an induced claw $K_{1,3}$ via an embedding $f$. The images $f(u)$ and $f(v)$ of two distinct leaves of the claw are each adjacent to the image $f(c_0)$ of the center, which places $f(u)$ and $f(v)$ in the same connected component of $G$. Because every connected component of $G$ is assumed to be a clique, any two distinct vertices in the same component must be adjacent, forcing $f(u)$ and $f(v)$ to be adjacent in $G$. However, this contradicts the fact that $f$ is an induced embedding, which requires non-adjacent vertices of $K_{1,3}$ to remain non-adjacent in $G$.
Suppose for contradiction that $G$ contains an induced claw, and identify its center and two leaves.
Assume for contradiction that $G$ is not claw-free, meaning there exists an induced subgraph embedding $f : K_{1,3} \hookrightarrow G$ from the complete bipartite graph $K_{1,3}$. The vertices of $K_{1,3}$ are represented as the sum type $\text{Fin } 1 \oplus \text{Fin } 3$. Designate $c_0 = \text{Sum.inl } 0$ as the center vertex (in the 1-element part) and $u = \text{Sum.inr } 0$, $v = \text{Sum.inr } 1$ as two distinct leaves (in the 3-element part).
intro ⟨f⟩ let c0 : Fin 1 ⊕ Fin 3 := Sum.inl 0 let u : Fin 1 ⊕ Fin 3 := Sum.inr 0 let v : Fin 1 ⊕ Fin 3 := Sum.inr 1
The images of both leaves, $f(u)$ and $f(v)$, are adjacent to the image of the center, $f(c_0)$, in $G$.
In the bipartite graph $K_{1,3}$, the center $c_0$ lies in the left part while $u$ and $v$ lie in the right part, so $c_0$ is adjacent to both $u$ and $v$ by definition of a complete bipartite graph (`completeBipartiteGraph_adj`). Because $f$ is an induced embedding, it preserves adjacency (`SimpleGraph.Embedding.map_adj_iff`), so $f(c_0)$ is adjacent to $f(u)$ and to $f(v)$ in $G$.
uses
SimpleGraph.Embedding.map_adj_iff,completeBipartiteGraph_adjhave hcu : G.Adj (f c0) (f u) := by rw [SimpleGraph.Embedding.map_adj_iff] simp [c0, u, completeBipartiteGraph_adj] have hcv : G.Adj (f c0) (f v) := by rw [SimpleGraph.Embedding.map_adj_iff] simp [c0, v, completeBipartiteGraph_adj]
The vertices $f(u)$ and $f(v)$ are not adjacent in $G$.
In $K_{1,3}$, the leaves $u$ and $v$ both lie in the right part, so they are not adjacent (`completeBipartiteGraph_adj`). Since $f$ is an induced embedding, it reflects adjacency (`SimpleGraph.Embedding.map_adj_iff`), meaning $f(u)$ and $f(v)$ cannot be adjacent in $G$.
uses
SimpleGraph.Embedding.map_adj_iff,completeBipartiteGraph_adjhave hnot : ¬ G.Adj (f u) (f v) := by rw [SimpleGraph.Embedding.map_adj_iff] simp [u, v, completeBipartiteGraph_adj]
The vertices $f(u)$ and $f(v)$ are distinct in $G$.
If $f(u) = f(v)$, the injectivity of the embedding $f$ would force $u = v$, which is $\text{Sum.inr } 0 = \text{Sum.inr } 1$. Since $0 \neq 1$ in $\text{Fin } 3$, this is impossible, so $f(u) \neq f(v)$.
have hne : f u ≠ f v := by intro h have := f.injective h dsimp [u, v] at this cases this
The vertices $f(u)$ and $f(v)$ belong to the same connected component of $G$.
By `SimpleGraph.ConnectedComponent.connectedComponentMk_eq_of_adj`, adjacent vertices share the same connected component. Since $f(u)$ is adjacent to $f(c_0)$, they lie in the same component; similarly, $f(v)$ and $f(c_0)$ share the same component. Transitivity of equality implies that $f(u)$ and $f(v)$ belong to the same connected component.
uses
SimpleGraph.ConnectedComponent.connectedComponentMk_eq_of_adjhave h_comp_u : G.connectedComponentMk (f u) = G.connectedComponentMk (f c0) := SimpleGraph.ConnectedComponent.connectedComponentMk_eq_of_adj hcu.symm have h_comp_v : G.connectedComponentMk (f v) = G.connectedComponentMk (f c0) := SimpleGraph.ConnectedComponent.connectedComponentMk_eq_of_adj hcv.symm have h_comp : G.connectedComponentMk (f u) = G.connectedComponentMk (f v) := h_comp_u.trans h_comp_v.symm
A contradiction arises because every connected component is a clique, concluding the proof.
Let $C$ be the connected component containing both $f(u)$ and $f(v)$. By the hypothesis that every connected component is a clique, any two distinct vertices in $C$ are adjacent in $G$. Since $f(u)$ and $f(v)$ are distinct vertices in $C$, they must be adjacent, which directly contradicts the fact that they are not adjacent.
let C := G.connectedComponentMk (f v) have hu_mem : f u ∈ C.supp := h_comp have hv_mem : f v ∈ C.supp := rfl have hadj : G.Adj (f u) (f v) := hclique C hu_mem hv_mem hne exact hnot hadj
SimpleGraph.Embedding.map_adj_iff- An induced graph embedding preserves and reflects adjacency: two vertices in the target graph are adjacent if and only if their preimages are adjacent in the source graph.
completeBipartiteGraph_adj- In a complete bipartite graph on $V \oplus W$, two vertices are adjacent if and only if one belongs to $V$ (the left part) and the other belongs to $W$ (the right part).
SimpleGraph.ConnectedComponent.connectedComponentMk_eq_of_adj- If two vertices in a graph are adjacent, they belong to the same connected component.
- In Lean's simple graph library, a vertex $w$ belongs to the support of a connected component $C$ (`w ∈ C.supp`) by definition when its component representative `G.connectedComponentMk w` equals $C$. Consequently, the equality of components established in line 28 directly proves membership in line 31 without any intermediate steps.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- Every finite graph whose connected components are cliques is claw-free. -/theorem op_1355_clique_components_is_claw_free {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (hclique : ∀ c : G.ConnectedComponent, G.IsClique c.supp) : IsClawFree G := by intro ⟨f⟩ let c0 : Fin 1 ⊕ Fin 3 := Sum.inl 0 let u : Fin 1 ⊕ Fin 3 := Sum.inr 0 let v : Fin 1 ⊕ Fin 3 := Sum.inr 1 have hcu : G.Adj (f c0) (f u) := by rw [SimpleGraph.Embedding.map_adj_iff] simp [c0, u, completeBipartiteGraph_adj] have hcv : G.Adj (f c0) (f v) := by rw [SimpleGraph.Embedding.map_adj_iff] simp [c0, v, completeBipartiteGraph_adj] have hnot : ¬ G.Adj (f u) (f v) := by rw [SimpleGraph.Embedding.map_adj_iff] simp [u, v, completeBipartiteGraph_adj] have hne : f u ≠ f v := by intro h have := f.injective h dsimp [u, v] at this cases this have h_comp_u : G.connectedComponentMk (f u) = G.connectedComponentMk (f c0) := SimpleGraph.ConnectedComponent.connectedComponentMk_eq_of_adj hcu.symm have h_comp_v : G.connectedComponentMk (f v) = G.connectedComponentMk (f c0) := SimpleGraph.ConnectedComponent.connectedComponentMk_eq_of_adj hcv.symm have h_comp : G.connectedComponentMk (f u) = G.connectedComponentMk (f v) := h_comp_u.trans h_comp_v.symm let C := G.connectedComponentMk (f v) have hu_mem : f u ∈ C.supp := h_comp have hv_mem : f v ∈ C.supp := rfl have hadj : G.Adj (f u) (f v) := hclique C hu_mem hv_mem hne exact hnot hadj