AFTD Auto-Formalizing Theoretical Domains

op_1355_clique_components_is_claw_free

theoremverified

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$.

  1. 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).

    lines 6–9

      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
  2. 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$.

    lines 10–15

    uses SimpleGraph.Embedding.map_adj_iff, completeBipartiteGraph_adj

      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]
  3. 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$.

    lines 16–18

    uses SimpleGraph.Embedding.map_adj_iff, completeBipartiteGraph_adj

      have hnot : ¬ G.Adj (f u) (f v) := by
        rw [SimpleGraph.Embedding.map_adj_iff]
        simp [u, v, completeBipartiteGraph_adj]
  4. 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)$.

    lines 19–23

      have hne : f u ≠ f v := by
        intro h
        have := f.injective h
        dsimp [u, v] at this
        cases this
  5. 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.

    lines 24–29

    uses SimpleGraph.ConnectedComponent.connectedComponentMk_eq_of_adj

      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
  6. 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.

    lines 30–34

      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.

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

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