is_claw_free_triple_neighbors
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
- not_p7_claw_free_dominating_pair_of_no_holeThe statement
p7_claw_free_dominating_pair_of_no_holeis false: The statement is FALSE. A concrete counterexample is the net graph (a… - not_is_pk_free_claw_free_hole_dominatingThe statement
is_pk_free_claw_free_hole_dominatingis false: The statement is false as written: it allows k = 4 and m = 3 (since k - 1 =… - claw_free_adj_of_neighborsIn any claw-free graph G, if a vertex x is adjacent to three pairwise distinct vertices u, v, and w, and w is adjacent to neither u nor v,…
- not_p7_claw_free_dominating_pair_of_no_holeThe statement
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.
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.
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
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.
apply hclaw let f : Fin 1 ⊕ Fin 3 → V := Sum.elim (fun _ => v) ![a,b,c]
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.
uses
Sum.elim_inl,congrArg,Sum.inl,Subsingleton.elim,Sum.elim_inrhave 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
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.
uses
completeBipartiteGraphrefine ⟨{ 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.
- On paper, checking that the four vertices {v, a, b, c} form an induced claw is immediate by inspection. In Lean, establishing the embedding requires an exhaustive case analysis over all 16 pairs of vertices in Fin 1 ⊕ Fin 3.
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.
/-- 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'']