claw_free_adj_of_neighbors
In 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, then u and v are adjacent.
Statement
theorem claw_free_adj_of_neighbors {V : Type*} (G : SimpleGraph V) (hclaw : IsClawFree G) (x u v w : V) (hu : G.Adj x u) (hv : G.Adj x v) (hw : G.Adj x w) (huv : u ≠ v) (huw : u ≠ w) (hvw : v ≠ w) (h_not_uw : ¬ G.Adj u w) (h_not_vw : ¬ G.Adj v w) : G.Adj u v
- Source
- arXiv:2611.09072 Claw-free minimal factor-critical and bicritical graphs, Lemma 3.1
- Verified
- 10 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- is_claw_free_triple_neighborsIn any claw-free graph, among any three distinct neighbors of a vertex, at least two are adjacent.
- 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 type and $G$ be a simple graph on $V$. Suppose $G$ is claw-free (IsClawFree G). Let $x, u, v, w \in V$ be vertices such that:
1. $x$ is adjacent to $u$ in $G$,
2. $x$ is adjacent to $v$ in $G$,
3. $x$ is adjacent to $w$ in $G$,
4. $u \neq v$,
5. $u \neq w$,
6. $v \neq w$,
7. $u$ is not adjacent to $w$ in $G$, and
8. $v$ is not adjacent to $w$ in $G$.
Then $u$ is adjacent to $v$ in $G$.
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
In a claw-free graph, any three pairwise distinct neighbors of a vertex must contain at least one adjacent pair. Since the third neighbor w is assumed to be adjacent to neither u nor v, the only remaining possibility is that u and v are adjacent.
At least one pair among u, v, and w is adjacent: G.Adj u v ∨ G.Adj u w ∨ G.Adj v w.
By the claw-free property (is_claw_free_triple_neighbors), the three distinct neighbors u, v, and w of vertex x cannot form an independent set of size 3, so at least one pair among them must be connected by an edge.
uses
is_claw_free_triple_neighborshave h := is_claw_free_triple_neighbors G hclaw x u v w hu hv hw huv hvw huwu and v are adjacent (G.Adj u v).
Propositional logic (tauto) resolves the disjunction: since w is adjacent to neither u (h_not_uw) nor v (h_not_vw), the only remaining alternative is that u is adjacent to v.
tauto
is_claw_free_triple_neighbors- In a claw-free graph, among any three pairwise distinct neighbors of a vertex, at least two must be adjacent.
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 a claw-free graph, if a vertex has three distinct neighbors and one is adjacent to neither of the other two, then the remaining two neighbors must be adjacent. -/theorem claw_free_adj_of_neighbors {V : Type*} (G : SimpleGraph V) (hclaw : IsClawFree G) (x u v w : V) (hu : G.Adj x u) (hv : G.Adj x v) (hw : G.Adj x w) (huv : u ≠ v) (huw : u ≠ w) (hvw : v ≠ w) (h_not_uw : ¬ G.Adj u w) (h_not_vw : ¬ G.Adj v w) : G.Adj u v := by have h := is_claw_free_triple_neighbors G hclaw x u v w hu hv hw huv hvw huw tauto