graph_collinear_middle_unique
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
- graph_interval_index_eq_choose_two_add_colFor every connected finite graph G on n vertices, the interval index Int(G) equals (n choose 2) + col(G).
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.
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.
uses
SimpleGraph.dist_commintro h2 rw [SimpleGraph.dist_comm (u := y) (v := x)] at h2 have h3 : G.dist x y = 0 := by omega
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).
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
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.
/-- 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)