AFTD Auto-Formalizing Theoretical Domains

graph_at_most_one_between

theoremverifiedformalization

In a connected graph G, if y lies between x and z and x lies between y and z, then x = y; hence among three distinct vertices, at most one lies between the other two.

Statement

theorem graph_at_most_one_between {V : Type*} (G : SimpleGraph V) (hconn : G.Connected)
    {x y z : V} (h1 : G.dist x y + G.dist y z = G.dist x z)
    (h2 : G.dist y x + G.dist x z = G.dist y z) : x = y
Formalizes
arXiv:2610.39966 Lemma 3
Verified
02 Nov 2026
Axioms
Classical.choiceQuot.soundpropext

Read back from the Lean

For any type V and any simple graph G on V, assuming G is connected (G.Connected), and for all vertices x, y, z : V, if G.dist x y + G.dist y z = G.dist x z and G.dist y x + G.dist x z = G.dist y z, then x = y.

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

To show that x = y when y lies between x and z and x lies between y and z in a connected graph G, we use the symmetry of the graph metric along with the two betweenness equations. Adding the equations shows that the distance between x and y must be zero. In a connected graph, two vertices with distance zero are identical, so x = y.

  1. The distance between x and y is 0. automation

    By the symmetry of graph distance (SimpleGraph.dist_comm), G.dist y x = G.dist x y. Substituting this into the two given betweenness equations, G.dist x y + G.dist y z = G.dist x z and G.dist y x + G.dist x z = G.dist y z, gives a system of linear equations in the non-negative integer distances. Adding them implies 2 * G.dist x y = 0, so G.dist x y = 0, which is closed by linear integer arithmetic (omega).

    lines 5–6

    uses SimpleGraph.dist_comm

      have hsymm : G.dist y x = G.dist x y := SimpleGraph.dist_comm
      have hdist : G.dist x y = 0 := by omega
  2. x = y

    In a connected graph, the distance between two vertices is 0 if and only if the vertices are equal (hconn.dist_eq_zero_iff). Since G.dist x y = 0, it follows that x = y.

    line 7

      exact hconn.dist_eq_zero_iff.mp hdist
SimpleGraph.dist_comm
In any simple graph, the distance between u and v equals the distance between v and 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

/-- At most one vertex lies between the other two among three distinct vertices in a connected graph. -/theorem graph_at_most_one_between {V : Type*} (G : SimpleGraph V) (hconn : G.Connected)    {x y z : V} (h1 : G.dist x y + G.dist y z = G.dist x z)    (h2 : G.dist y x + G.dist x z = G.dist y z) : x = y := by  have hsymm : G.dist y x = G.dist x y := SimpleGraph.dist_comm  have hdist : G.dist x y = 0 := by omega  exact hconn.dist_eq_zero_iff.mp hdist
See it in the graphDiscuss this resultChallenge it