AFTD Auto-Formalizing Theoretical Domains

graph_collinear_middle_unique

theoremverifiedformalization

Among three pairwise distinct vertices x, y, z in a connected graph G, if y lies between x and z (i.e. d(x,y) + d(y,z) = d(x,z)), then x cannot lie between y and z (i.e. d(y,x) + d(x,z) ≠ d(y,z)).

Statement

theorem graph_collinear_middle_unique {V : Type*} (G : SimpleGraph V) (hG : G.Connected)
    {x y z : V} (hxy : x ≠ y) (hyz : y ≠ z) (hxz : x ≠ z)
    (h1 : G.dist x y + G.dist y z = G.dist x z) :
    G.dist y x + G.dist x z ≠ G.dist y z
Formalizes
arXiv:2610.39966 Lemma 3
Verified
31 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1

Read back from the Lean

For any type V, any connected simple graph G on V, and any vertices x, y, z : V: if x ≠ y, y ≠ z, x ≠ z, and the graph distance from x to y plus the graph distance from y to z equals the graph distance from x to z (G.dist x y + G.dist y z = G.dist x z), then the graph distance from y to x plus the graph distance from x to z does not equal the graph distance from y to z (G.dist y x + G.dist x z ≠ G.dist y z).

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

The proof proceeds by contradiction. Assuming that x also lies between y and z, we have d(y, x) + d(x, z) = d(y, z). Using distance symmetry, this becomes d(x, y) + d(x, z) = d(y, z), which combined with the hypothesis d(x, y) + d(y, z) = d(x, z) forces 2 · d(x, y) = 0, so d(x, y) = 0. In a connected graph, zero distance implies x = y, contradicting the assumption that x and y are distinct.

  1. Assuming for contradiction that x lies between y and z, the distance between x and y must be 0.

    Assume for contradiction that x lies between y and z, meaning d(y, x) + d(x, z) = d(y, z) (hypothesis h2). By the symmetry of graph distance (SimpleGraph.dist_comm), d(y, x) = d(x, y), so this becomes d(x, y) + d(x, z) = d(y, z). Substituting the given betweenness equation d(x, y) + d(y, z) = d(x, z) (hypothesis h1) into this relation yields 2 · d(x, y) + d(y, z) = d(y, z), which forces d(x, y) = 0. Linear arithmetic over ℕ (via omega) discharges this deduction.

    lines 6–8

    uses SimpleGraph.dist_comm

      intro h2
      rw [SimpleGraph.dist_comm (u := y) (v := x)] at h2
      have h3 : G.dist x y = 0 := by omega
  2. The equality d(x, y) = 0 contradicts the assumption that x ≠ y, completing the proof.

    In a connected graph, two vertices have distance zero if and only if they are equal (hG.dist_eq_zero_iff). Hence d(x, y) = 0 implies x = y, which contradicts the hypothesis that x ≠ y (hypothesis hxy).

    line 9

      exact hxy (hG.dist_eq_zero_iff.mp h3)
SimpleGraph.dist_comm
In any simple graph, the distance between two vertices is symmetric: d(u, v) = d(v, u).

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 connected graph, at most one of three pairwise distinct vertices lies between the other two (Lemma 3). -/theorem graph_collinear_middle_unique {V : Type*} (G : SimpleGraph V) (hG : G.Connected)    {x y z : V} (hxy : x ≠ y) (hyz : y ≠ z) (hxz : x ≠ z)    (h1 : G.dist x y + G.dist y z = G.dist x z) :    G.dist y x + G.dist x z ≠ G.dist y z := by  intro h2  rw [SimpleGraph.dist_comm (u := y) (v := x)] at h2  have h3 : G.dist x y = 0 := by omega  exact hxy (hG.dist_eq_zero_iff.mp h3)
See it in the graphDiscuss this resultChallenge it