exists_dist_eq_three_of_three_le_diam
If the diameter of a finite connected graph is at least 3, then some pair of vertices is at distance exactly 3.
Statement
theorem exists_dist_eq_three_of_three_le_diam {V : Type} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (hd : 3 ≤ G.diam) : ∃ x y : V, G.dist x y = 3
- Source
- step towards exists_dist_three_lly_curvature_le_cut
- Verified
- 18 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- graph_lly_curvature_le_two_div_distFor distinct vertices x, y of a finite connected graph, κ_LLY(x, y) ≤ 2/d(x, y).
The proof, explained
Since the finite graph has diameter at least 3, there exist vertices u and v realizing the diameter, connected by a shortest walk p of length at least 3. Choosing u and the vertex w at distance 3 along p (i.e. p.getVert 3), the prefix walk of length 3 shows that dist(u, w) ≤ 3. If dist(u, w) ≤ 2, bypassing the prefix with a shorter path would yield a walk from u to v of length at most 2 + (length(p) - 3) < length(p), contradicting that p is a shortest walk.
The vertex set V has at least two elements (it is not a subsingleton).
If V had at most one vertex, the diameter of G would be 0 by `SimpleGraph.diam_eq_zero.mpr`, contradicting the hypothesis that the diameter is at least 3.
uses
SimpleGraph.diam_eq_zero.mpr,Or.inrhave hns : ¬ Subsingleton V := by intro hs have h0 : G.diam = 0 := SimpleGraph.diam_eq_zero.mpr (Or.inr hs) omega
The vertex set V is nonempty.
If V were empty, then any two vertices would vacuously be equal, making V a subsingleton, which contradicts what was just shown.
haveI : Nonempty V := by by_contra h exact hns ⟨fun a b => (h ⟨a⟩).elim⟩
There exists a pair of vertices u, v at distance at least 3, so in particular dist(u, v) ≠ 0.
Because V is nonempty and finite, there exist vertices u and v whose distance equals the diameter of G (`SimpleGraph.exists_dist_eq_diam`). Since the diameter is at least 3, dist(u, v) ≥ 3, which implies dist(u, v) ≠ 0.
uses
SimpleGraph.exists_dist_eq_diamobtain ⟨u, v, huv⟩ := SimpleGraph.exists_dist_eq_diam (G := G) have h3 : 3 ≤ G.dist u v := by rw [huv]; exact hd have hne0 : G.dist u v ≠ 0 := by omega
There exists a walk p from u to v of length equal to dist(u, v) ≥ 3.
Because dist(u, v) ≠ 0, there exists a shortest walk p from u to v whose length equals dist(u, v) (`SimpleGraph.exists_walk_of_dist_ne_zero`). Since dist(u, v) ≥ 3, the length of p is at least 3.
uses
SimpleGraph.exists_walk_of_dist_ne_zeroobtain ⟨p, hp⟩ := SimpleGraph.exists_walk_of_dist_ne_zero hne0 have hlen : 3 ≤ p.length := by rw [hp]; exact h3
It suffices to show that dist(u, p.getVert 3) ≤ 3 and 3 ≤ dist(u, p.getVert 3).
We choose u and the third vertex along the walk p (p.getVert 3) as the candidate pair. By antisymmetry of inequality (`le_antisymm`), showing both inequalities establishes that their distance is exactly 3.
uses
le_antisymmrefine ⟨u, p.getVert 3, le_antisymm ?_ ?_⟩The distance from u to p.getVert 3 is at most 3.
The initial segment `p.take 3` is a walk from u to p.getVert 3. Since the length of p is at least 3, the length of this prefix is min(3, length(p)) = 3 by `SimpleGraph.Walk.take_length`. Since distance is bounded by the length of any connecting walk (`SimpleGraph.dist_le`), dist(u, p.getVert 3) ≤ 3.
uses
SimpleGraph.Walk.take_length,SimpleGraph.dist_le· have ht : (p.take 3).length = 3 := by rw [SimpleGraph.Walk.take_length] omega calc G.dist u (p.getVert 3) ≤ (p.take 3).length := SimpleGraph.dist_le _ _ = 3 := ht
The distance from u to p.getVert 3 is at least 3, which finishes the proof.
Suppose for contradiction that dist(u, p.getVert 3) < 3, so dist(u, p.getVert 3) ≤ 2. The remaining suffix `p.drop 3` is a walk from p.getVert 3 to v of length length(p) - 3 (`SimpleGraph.Walk.drop_length`), so dist(p.getVert 3, v) ≤ length(p) - 3 by `SimpleGraph.dist_le`. Applying the triangle inequality (`SimpleGraph.Reachable.dist_triangle_left`), we get dist(u, v) ≤ dist(u, p.getVert 3) + dist(p.getVert 3, v) ≤ 2 + (length(p) - 3) = length(p) - 1. But length(p) = dist(u, v), so dist(u, v) ≤ dist(u, v) - 1, which is impossible.
uses
SimpleGraph.dist_le,SimpleGraph.Walk.drop_length,SimpleGraph.Reachable.dist_triangle_left,SimpleGraph.Walk.reachable· by_contra hcon have hcon2 : G.dist u (p.getVert 3) ≤ 2 := by omega have hdrop : G.dist (p.getVert 3) v ≤ (p.drop 3).length := SimpleGraph.dist_le _ rw [SimpleGraph.Walk.drop_length] at hdrop have htri : G.dist u v ≤ G.dist u (p.getVert 3) + G.dist (p.getVert 3) v := SimpleGraph.Reachable.dist_triangle_left (p.take 3).reachable v omega
le_antisymm- In a partial order, if a ≤ b and b ≤ a, then a = b.
Or.inr- The second constructor of `Or`, proving `A ∨ B` given a proof of `B`.
SimpleGraph.diam_eq_zero.mpr- A graph has diameter 0 if its extended diameter is infinite or its vertex type is a subsingleton.
SimpleGraph.dist_le- The distance between the endpoints of a walk is at most the length of the walk.
SimpleGraph.exists_dist_eq_diam- In any nonempty finite graph, there exists a pair of vertices whose distance equals the diameter of the graph.
SimpleGraph.exists_walk_of_dist_ne_zero- If two vertices have nonzero distance, there exists a walk between them whose length equals their distance (a geodesic walk).
SimpleGraph.Reachable.dist_triangle_left- The triangle inequality for graph distance: if u can reach v, then dist(u, w) ≤ dist(u, v) + dist(v, w).
SimpleGraph.Walk.drop_length- The length of the suffix of a walk p obtained by dropping the first n steps is length(p) - n.
SimpleGraph.Walk.reachable- A walk from u to v shows that u can reach v.
SimpleGraph.Walk.take_length- The length of the prefix of a walk p obtained by taking at most n steps is min(n, length(p)).
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.
/-- A finite graph whose diameter is at least 3 has a pair of vertices at distance exactly 3. -/theorem exists_dist_eq_three_of_three_le_diam {V : Type} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (hd : 3 ≤ G.diam) : ∃ x y : V, G.dist x y = 3 := by have hns : ¬ Subsingleton V := by intro hs have h0 : G.diam = 0 := SimpleGraph.diam_eq_zero.mpr (Or.inr hs) omega haveI : Nonempty V := by by_contra h exact hns ⟨fun a b => (h ⟨a⟩).elim⟩ obtain ⟨u, v, huv⟩ := SimpleGraph.exists_dist_eq_diam (G := G) have h3 : 3 ≤ G.dist u v := by rw [huv]; exact hd have hne0 : G.dist u v ≠ 0 := by omega obtain ⟨p, hp⟩ := SimpleGraph.exists_walk_of_dist_ne_zero hne0 have hlen : 3 ≤ p.length := by rw [hp]; exact h3 refine ⟨u, p.getVert 3, le_antisymm ?_ ?_⟩ · have ht : (p.take 3).length = 3 := by rw [SimpleGraph.Walk.take_length] omega calc G.dist u (p.getVert 3) ≤ (p.take 3).length := SimpleGraph.dist_le _ _ = 3 := ht · by_contra hcon have hcon2 : G.dist u (p.getVert 3) ≤ 2 := by omega have hdrop : G.dist (p.getVert 3) v ≤ (p.drop 3).length := SimpleGraph.dist_le _ rw [SimpleGraph.Walk.drop_length] at hdrop have htri : G.dist u v ≤ G.dist u (p.getVert 3) + G.dist (p.getVert 3) v := SimpleGraph.Reachable.dist_triangle_left (p.take 3).reachable v omega