AFTD Auto-Formalizing Theoretical Domains

simple_graph_disjoint_neighbors_of_dist_three

theoremverified

In any simple graph, two vertices at distance 3 share no common neighbors.

Statement

theorem simple_graph_disjoint_neighbors_of_dist_three
    {V : Type*} (G : SimpleGraph V) (u v : V)
    (hdist : G.dist u v = 3) (w : V) :
    ¬ (G.Adj u w ∧ G.Adj v w)
Source
arXiv:2611.08244 Theorem 4.1
Verified
06 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1

Read back from the Lean

For any type V, any simple graph G on V, any vertices u, v : V such that the graph distance G.dist u v equals 3, and any vertex w : V, it is not the case that w is adjacent to both u and v in G (that is, u and v share no common neighbor).

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

We argue by contradiction: suppose $u$ and $v$ share a common neighbor $w$. Traversing the edge from $u$ to $w$ followed by the reversed edge from $w$ to $v$ yields a walk of length 2 between $u$ and $v$. The distance between two vertices is bounded by the length of any walk connecting them, which implies that the distance between $u$ and $v$ is at most 2. This contradicts the assumption that their distance is 3.

  1. Assume for contradiction that $u$ and $v$ share a common neighbor $w$.

    We introduce the assumption that $w$ is adjacent to both $u$ and $v$, splitting the conjunction into hypotheses that $u \sim w$ and $v \sim w$.

    line 6

      rintro ⟨hu, hv⟩
  2. The distance between $u$ and $v$ is at most 2.

    Concatenating the edge between $u$ and $w$ with the reversed edge between $w$ and $v$ forms a walk of length 2 from $u$ to $v$. By `G.dist_le`, the graph distance between $u$ and $v$ cannot exceed the length of this walk, giving $\operatorname{dist}(u, v) \le 2$.

    lines 7–8

    uses G.dist_le

      have hle := G.dist_le (hu.toWalk.append hv.symm.toWalk)
      simp at hle
  3. Contradiction.

    We have $\operatorname{dist}(u, v) = 3$ by assumption and $\operatorname{dist}(u, v) \le 2$ from the length-2 walk. Linear integer arithmetic detects the impossibility $3 \le 2$ and closes the proof.

    line 9

      omega
G.dist_le
The distance between two vertices in a simple graph is at most the length of any walk connecting them.

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

/-- Two vertices at distance 3 in a simple graph do not share any common neighbor. -/theorem simple_graph_disjoint_neighbors_of_dist_three    {V : Type*} (G : SimpleGraph V) (u v : V)    (hdist : G.dist u v = 3) (w : V) :    ¬ (G.Adj u w ∧ G.Adj v w) := by  rintro ⟨hu, hv⟩  have hle := G.dist_le (hu.toWalk.append hv.symm.toWalk)  simp at hle  omega
See it in the graphDiscuss this resultChallenge it