AFTD Auto-Formalizing Theoretical Domains

exists_dist_eq_three_of_three_le_diam

theoremverified

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

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.

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

    lines 7–10

    uses SimpleGraph.diam_eq_zero.mpr, Or.inr

      have hns : ¬ Subsingleton V := by
        intro hs
        have h0 : G.diam = 0 := SimpleGraph.diam_eq_zero.mpr (Or.inr hs)
        omega
  2. 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.

    lines 11–13

      haveI : Nonempty V := by
        by_contra h
        exact hns ⟨fun a b => (h ⟨a⟩).elim⟩
  3. 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.

    lines 14–16

    uses SimpleGraph.exists_dist_eq_diam

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

    lines 17–18

    uses SimpleGraph.exists_walk_of_dist_ne_zero

      obtain ⟨p, hp⟩ := SimpleGraph.exists_walk_of_dist_ne_zero hne0
      have hlen : 3 ≤ p.length := by rw [hp]; exact h3
  5. 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.

    line 19

    uses le_antisymm

      refine ⟨u, p.getVert 3, le_antisymm ?_ ?_⟩
  6. 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.

    lines 20–24

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

    lines 25–31

    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

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