simple_graph_disjoint_neighbors_of_dist_three
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
- simple_graph_adj_row_add_is_binary_of_dist_threeFor two vertices at distance 3 in a finite simple graph, the sum of their rows in the adjacency matrix over ℝ is a (0,1)-vector.
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.
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$.
rintro ⟨hu, hv⟩
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$.
uses
G.dist_lehave hle := G.dist_le (hu.toWalk.append hv.symm.toWalk) simp at hle
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.
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
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.
/-- 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