graph_at_most_one_between
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.
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).
uses
SimpleGraph.dist_commhave hsymm : G.dist y x = G.dist x y := SimpleGraph.dist_comm have hdist : G.dist x y = 0 := by omega
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.
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
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.
/-- 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