AFTD Auto-Formalizing Theoretical Domains

claw_free_adj_of_neighbors

theoremverified

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.

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

    line 7

    uses is_claw_free_triple_neighbors

      have h := is_claw_free_triple_neighbors G hclaw x u v w hu hv hw huv hvw huw
  2. u 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.

    line 8

      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

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