AFTD Auto-Formalizing Theoretical Domains

is_claw_free_triple_neighbors

theoremverified

In any claw-free graph, among any three distinct neighbors of a vertex, at least two are adjacent.

Statement

theorem is_claw_free_triple_neighbors {V : Type*} (G : SimpleGraph V) (hclaw : IsClawFree G)
    (v : V) (a b c : V) (ha : G.Adj v a) (hb : G.Adj v b) (hc : G.Adj v c)
    (hab : a ≠ b) (hbc : b ≠ c) (hac : a ≠ c) :
    G.Adj a b ∨ G.Adj a c ∨ G.Adj b c
Source
step towards op_292_cop_number_p7_claw_free
Verified
26 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.
Used by 3

The proof, explained

The proof argues by contradiction: if three distinct neighbors a, b, c of a vertex v shared no edges among themselves, the induced subgraph on {v, a, b, c} would be isomorphic to the claw graph K₁,₃. An explicit mapping from Fin 1 ⊕ Fin 3 to V is defined, sending the central vertex to v and the three leaves to a, b, and c. Showing this mapping is injective and preserves both adjacency and non-adjacency exhibits K₁,₃ as an induced subgraph of G, directly contradicting the assumption that G is claw-free.

  1. Assuming for contradiction that no two of a, b, c are adjacent, every pair among them is non-adjacent in both directions.

    We assume the negation of the conclusion for contradiction (`by_contra`). Pushing the negation inward yields ¬ G.Adj a b, ¬ G.Adj a c, and ¬ G.Adj b c. By the symmetry of adjacency in simple graphs, their reversed versions (¬ G.Adj b a, ¬ G.Adj c a, ¬ G.Adj c b) also hold.

    lines 6–11

      by_contra h
      push Not at h
      obtain ⟨hab', hac', hbc'⟩ := h
      have hab'' : ¬ G.Adj b a := fun hh => hab' hh.symm
      have hac'' : ¬ G.Adj c a := fun hh => hac' hh.symm
      have hbc'' : ¬ G.Adj c b := fun hh => hbc' hh.symm
  2. To derive a contradiction, it suffices to exhibit an induced copy of the claw graph K₁,₃ in G, for which we define a candidate vertex mapping f.

    By definition of `IsClawFree`, G contains no induced claw (K₁,₃, formalized as `completeBipartiteGraph (Fin 1) (Fin 3)`). Applying `hclaw` reduces the goal of deriving `False` to finding an induced subgraph embedding of K₁,₃ into G. We define the candidate map f : Fin 1 ⊕ Fin 3 → V sending the unique vertex in Fin 1 to v, and the three vertices in Fin 3 to a, b, and c.

    lines 12–13

      apply hclaw
      let f : Fin 1 ⊕ Fin 3 → V := Sum.elim (fun _ => v) ![a,b,c]
  3. The vertex mapping f is injective.

    Assuming f x = f y, we perform case analysis on x and y in Fin 1 ⊕ Fin 3: when both are in Fin 1, they are equal by `Subsingleton.elim` and `congrArg`; when one is in Fin 1 and the other in Fin 3, f maps one to v and the other to an element of {a, b, c}, which is impossible because v is adjacent to a, b, c and simple graphs have no self-loops (`ha.ne`, `hb.ne`, `hc.ne`); when both are in Fin 3, f maps to {a, b, c}, which are pairwise distinct by hypothesis (`hab`, `hbc`, `hac`), forcing x = y.

    lines 14–36

    uses Sum.elim_inl, congrArg, Sum.inl, Subsingleton.elim, Sum.elim_inr

      have hf_inj : Function.Injective f := by
        intro x y hxy
        rcases x with i | i <;> rcases y with j | j
        · simp only [f, Sum.elim_inl] at hxy
          exact congrArg Sum.inl (Subsingleton.elim i j)
        · fin_cases i
          fin_cases j <;> simp only [f, Sum.elim_inr] at hxy
          · exact absurd hxy ha.ne
          · exact absurd hxy hb.ne
          · exact absurd hxy hc.ne
        · fin_cases i <;> fin_cases j <;> simp only [f, Sum.elim_inr] at hxy
          · exact absurd hxy.symm ha.ne
          · exact absurd hxy.symm hb.ne
          · exact absurd hxy.symm hc.ne
        · fin_cases i <;> fin_cases j <;> simp only [f, Sum.elim_inr] at hxy ⊢
          all_goals first
            | rfl
            | exact absurd hxy hab
            | exact absurd hxy hab.symm
            | exact absurd hxy hac
            | exact absurd hxy hac.symm
            | exact absurd hxy hbc
            | exact absurd hxy hbc.symm
  4. The map f defines an induced subgraph embedding of K₁,₃ into G, completing the proof.

    We package f and its injectivity into a graph embedding (`RelEmbedding`). It remains to show that two vertices are adjacent in K₁,₃ if and only if their images under f are adjacent in G. An exhaustive check of all 16 pairs of vertices using `fin_cases` resolves each case by simplifying with the definition of `completeBipartiteGraph`, the adjacencies between v and a, b, c, and the assumed non-adjacencies among a, b, c.

    lines 37–40

    uses completeBipartiteGraph

      refine ⟨{ toFun := f, inj' := hf_inj, map_rel_iff' := ?_ }⟩
      rintro (i | i) (j | j) <;> fin_cases i <;> fin_cases j <;>
        simp [f, completeBipartiteGraph, ha, hb, hc, ha.symm, hb.symm, hc.symm,
          hab', hac', hbc', hab'', hac'', hbc'']
Sum.elim_inl
Applying `Sum.elim f g` to a left summand `Sum.inl x` evaluates to `f x`.
Sum.elim_inr
Applying `Sum.elim f g` to a right summand `Sum.inr x` evaluates to `g x`.
congrArg
If two arguments are equal, a function applied to them yields equal values: a₁ = a₂ implies f a₁ = f a₂.
Sum.inl
The canonical inclusion of an element into the left summand of a direct sum type α ⊕ β.
Subsingleton.elim
In any subsingleton type (a type with at most one element, such as Fin 1), any two elements are equal.
completeBipartiteGraph
The complete bipartite graph on vertex types V and W, whose edges are exactly the pairs with one vertex in V and the other in W.

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

/-- In any claw-free graph, among any three distinct neighbors of a vertex, at least two are adjacent. -/theorem is_claw_free_triple_neighbors {V : Type*} (G : SimpleGraph V) (hclaw : IsClawFree G)    (v : V) (a b c : V) (ha : G.Adj v a) (hb : G.Adj v b) (hc : G.Adj v c)    (hab : a ≠ b) (hbc : b ≠ c) (hac : a ≠ c) :    G.Adj a b ∨ G.Adj a c ∨ G.Adj b c := by  by_contra h  push Not at h  obtain ⟨hab', hac', hbc'⟩ := h  have hab'' : ¬ G.Adj b a := fun hh => hab' hh.symm  have hac'' : ¬ G.Adj c a := fun hh => hac' hh.symm  have hbc'' : ¬ G.Adj c b := fun hh => hbc' hh.symm  apply hclaw  let f : Fin 1 ⊕ Fin 3 → V := Sum.elim (fun _ => v) ![a,b,c]  have hf_inj : Function.Injective f := by    intro x y hxy    rcases x with i | i <;> rcases y with j | j    · simp only [f, Sum.elim_inl] at hxy      exact congrArg Sum.inl (Subsingleton.elim i j)    · fin_cases i      fin_cases j <;> simp only [f, Sum.elim_inr] at hxy      · exact absurd hxy ha.ne      · exact absurd hxy hb.ne      · exact absurd hxy hc.ne    · fin_cases i <;> fin_cases j <;> simp only [f, Sum.elim_inr] at hxy      · exact absurd hxy.symm ha.ne      · exact absurd hxy.symm hb.ne      · exact absurd hxy.symm hc.ne    · fin_cases i <;> fin_cases j <;> simp only [f, Sum.elim_inr] at hxy ⊢      all_goals first        | rfl        | exact absurd hxy hab        | exact absurd hxy hab.symm        | exact absurd hxy hac        | exact absurd hxy hac.symm        | exact absurd hxy hbc        | exact absurd hxy hbc.symm  refine ⟨{ toFun := f, inj' := hf_inj, map_rel_iff' := ?_ }⟩  rintro (i | i) (j | j) <;> fin_cases i <;> fin_cases j <;>    simp [f, completeBipartiteGraph, ha, hb, hc, ha.symm, hb.symm, hc.symm,      hab', hac', hbc', hab'', hac'', hbc'']
See it in the graphDiscuss this resultChallenge it