five_vertex_t_star_dist_eq
In the T-graph: d(0,1) = 1, d(0,2) = 2, d(3,1) = 2, d(4,1) = 2, d(3,2) = d(4,2) = 3.
Statement
theorem five_vertex_t_star_dist_eq :
five_vertex_t_star.dist 0 1 = 1 ∧ five_vertex_t_star.dist 0 2 = 2 ∧
five_vertex_t_star.dist 3 1 = 2 ∧ five_vertex_t_star.dist 4 1 = 2 ∧
five_vertex_t_star.dist 3 2 = 3 ∧ five_vertex_t_star.dist 4 2 = 3- Source
- step towards lly_positive_edge_connectivity_threshold_five
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- five_vertex_t_starThe tree on 5 vertices with edges 0–1, 0–3, 0–4, 1–2: the path 3–0–1–2 with an extra leaf 4 attached at 0.
- five_vertex_t_star_adj_decidableAdjacency in the T-graph is decidable.
- Used by 4
- lly_positive_edge_connectivity_threshold_fivec(5) = 2: every connected graph on 5 vertices with edge-connectivity at least 2 has positive Lin–Lu–Yau curvature on every edge, while the…
- five_vertex_t_star_wasserstein_leFor the T-graph and α in [2/5, 1], the explicit plan π(0,0)=(1−α)/2, π(0,1)=(5α−2)/3, π(0,2)=(1−α)/6, π(1,2)=(1−α)/3, π(3,1)=(1−α)/3,…
- lly_five_vertex_t_star_curvatureFor the tree on 5 vertices with edges 0–1, 0–3, 0–4, 1–2 one has κ_LLY(0,1) = −1/3.
- five_vertex_t_star_wasserstein_geFor the T-graph and α in [0,1], 4/3 − α/3 ≤ W(μ_0^α, μ_1^α), because f(v) = d(v,2) is 1-Lipschitz and Σ f μ_0^α − Σ f μ_1^α = (2α +…
The proof, explained
The theorem calculates the shortest-path distances between six pairs of vertices in the 5-vertex tree five_vertex_t_star, whose central hub 0 connects to 1, 3, and 4, with 1 further connected to 2. Distances between adjacent vertices are determined immediately from the adjacency relation. Distances of 2 (d(0,2), d(3,1), and d(4,1)) are bounded above by the triangle inequality and below by non-adjacency. Finally, the distances d(3,2) and d(4,2) are bounded above by 3 via path 3-0-2 (or 4-0-2), while any walk of length at most 2 is ruled out by exhaustive search because 0 is the unique neighbor of 3 and 4 but is not adjacent to 2.
Every walk of length at most 2 connects equal vertices, adjacent vertices, or vertices that share a common neighbor.
We proceed by case analysis on the structure of the walk p. If p is empty (length 0), the endpoints u and v are identical. If p consists of a single edge followed by the empty walk (length 1), u and v are adjacent. If p consists of two edges followed by the empty walk (length 2), the intermediate vertex witnesses a common neighbor of u and v. If p has three or more edges, its length is at least 3, which contradicts the hypothesis that the length is at most 2.
uses
Or.inl,Or.inr,SimpleGraph.Walk.length_conscases p with | nil => exact Or.inl rfl | cons h1 q => cases q with | nil => exact Or.inr (Or.inl h1) | cons h2 r => cases r with | nil => exact Or.inr (Or.inr ⟨_, h1, h2⟩) | cons h3 s => simp only [SimpleGraph.Walk.length_cons] at hp omega
The graph five_vertex_t_star is connected, and the distances d(0,1), d(1,2), d(3,0), and d(4,0) are all 1.
Graph connectivity is verified by finite computation (`decide`). For each vertex pair (0,1), (1,2), (3,0), and (4,0), the distance in a graph is 1 if and only if the vertices are adjacent (using `SimpleGraph.dist_eq_one_iff_adj`, combined with symmetry `SimpleGraph.dist_comm` where needed). Each corresponding adjacency check is directly decided from the edge relations defining five_vertex_t_star.
uses
SimpleGraph.dist_eq_one_iff_adj,SimpleGraph.dist_commhave hconn : five_vertex_t_star.Connected := by decide have d01 : five_vertex_t_star.dist 0 1 = 1 := by rw [SimpleGraph.dist_eq_one_iff_adj] decide have d12 : five_vertex_t_star.dist 1 2 = 1 := by rw [SimpleGraph.dist_eq_one_iff_adj] decide have d30 : five_vertex_t_star.dist 3 0 = 1 := by rw [SimpleGraph.dist_comm, SimpleGraph.dist_eq_one_iff_adj] decide have d40 : five_vertex_t_star.dist 4 0 = 1 := by rw [SimpleGraph.dist_comm, SimpleGraph.dist_eq_one_iff_adj] decide
The distance d(0, 2) equals 2.
By the triangle inequality through vertex 1, d(0, 2) ≤ d(0, 1) + d(1, 2) = 1 + 1 = 2. In the other direction, since 0 ≠ 2 and 0 is not adjacent to 2 (both verified by finite computation), the distance is strictly greater than 1. Combining these two inequalities yields d(0, 2) = 2.
have d02 : five_vertex_t_star.dist 0 2 = 2 := by have hle : five_vertex_t_star.dist 0 2 ≤ 2 := by have := hconn.dist_triangle (u := 0) (v := 1) (w := 2) omega have hlt : 1 < five_vertex_t_star.dist 0 2 := hconn.one_lt_dist_of_ne_of_not_adj (by decide) (by decide) omega
The distance d(3, 1) equals 2.
By the triangle inequality through vertex 0, d(3, 1) ≤ d(3, 0) + d(0, 1) = 1 + 1 = 2. Conversely, because 3 ≠ 1 and 3 is not adjacent to 1 (both checked by `decide`), the distance is strictly greater than 1. Thus d(3, 1) = 2.
have d31 : five_vertex_t_star.dist 3 1 = 2 := by have hle : five_vertex_t_star.dist 3 1 ≤ 2 := by have := hconn.dist_triangle (u := 3) (v := 0) (w := 1) omega have hlt : 1 < five_vertex_t_star.dist 3 1 := hconn.one_lt_dist_of_ne_of_not_adj (by decide) (by decide) omega
The distance d(4, 1) equals 2.
By the triangle inequality through vertex 0, d(4, 1) ≤ d(4, 0) + d(0, 1) = 1 + 1 = 2. Conversely, since 4 ≠ 1 and 4 is not adjacent to 1, the distance is strictly greater than 1. Thus d(4, 1) = 2.
have d41 : five_vertex_t_star.dist 4 1 = 2 := by have hle : five_vertex_t_star.dist 4 1 ≤ 2 := by have := hconn.dist_triangle (u := 4) (v := 0) (w := 1) omega have hlt : 1 < five_vertex_t_star.dist 4 1 := hconn.one_lt_dist_of_ne_of_not_adj (by decide) (by decide) omega
The distance d(3, 2) equals 3.
The triangle inequality through vertex 0 gives d(3, 2) ≤ d(3, 0) + d(0, 2) = 1 + 2 = 3. For the lower bound, suppose for contradiction that d(3, 2) ≤ 2. In a connected graph, there exists a walk from 3 to 2 realizing the distance, so its length is at most 2. By our characterization lemma, this requires 3 = 2, adjacency of 3 and 2, or a common neighbor between 3 and 2. Lean's `decide` tactic checks every vertex of the finite graph and refutes all three cases (3's only neighbor is 0, and 0 is not adjacent to 2). This contradiction implies ¬(d(3, 2) ≤ 2), and linear arithmetic concludes d(3, 2) = 3.
uses
five_vertex_t_star_dist_eq_walk_length_le_twohave d32 : five_vertex_t_star.dist 3 2 = 3 := by have hle : five_vertex_t_star.dist 3 2 ≤ 3 := by have := hconn.dist_triangle (u := 3) (v := 0) (w := 2) omega have hgt : ¬ (five_vertex_t_star.dist 3 2 ≤ 2) := by intro hle2 obtain ⟨p, hp⟩ := hconn.exists_walk_length_eq_dist 3 2 have hp2 : p.length ≤ 2 := by omega have hcases := five_vertex_t_star_dist_eq_walk_length_le_two p hp2 revert hcases decide omega
The distance d(4, 2) equals 3.
Similarly, the triangle inequality through vertex 0 gives d(4, 2) ≤ d(4, 0) + d(0, 2) = 1 + 2 = 3. To show d(4, 2) > 2, assume for contradiction d(4, 2) ≤ 2. A shortest walk from 4 to 2 has length at most 2, which by the characterization lemma would mean 4 = 2, adjacency of 4 and 2, or a common neighbor. An exhaustive evaluation (`decide`) across all five vertices confirms none of these hold, since 4's only neighbor is 0 and 0 is not adjacent to 2. Hence d(4, 2) = 3.
uses
five_vertex_t_star_dist_eq_walk_length_le_twohave d42 : five_vertex_t_star.dist 4 2 = 3 := by have hle : five_vertex_t_star.dist 4 2 ≤ 3 := by have := hconn.dist_triangle (u := 4) (v := 0) (w := 2) omega have hgt : ¬ (five_vertex_t_star.dist 4 2 ≤ 2) := by intro hle2 obtain ⟨p, hp⟩ := hconn.exists_walk_length_eq_dist 4 2 have hp2 : p.length ≤ 2 := by omega have hcases := five_vertex_t_star_dist_eq_walk_length_le_two p hp2 revert hcases decide omega
All six distance equations hold simultaneously.
We assemble the six verified distances—d(0,1) = 1, d(0,2) = 2, d(3,1) = 2, d(4,1) = 2, d(3,2) = 3, and d(4,2) = 3—into the target conjunction.
exact ⟨d01, d02, d31, d41, d32, d42⟩
Or.inl- From a proof of the left disjunct, infer the disjunction.
Or.inr- From a proof of the right disjunct, infer the disjunction.
SimpleGraph.Walk.length_cons- The length of a walk formed by prepending an edge to a walk is the tail walk's length plus one.
SimpleGraph.dist_eq_one_iff_adj- The graph distance between two vertices is 1 if and only if they are adjacent.
SimpleGraph.dist_comm- Graph distance is symmetric: d(u, v) = d(v, u).
five_vertex_t_star_dist_eq_walk_length_le_two- Any walk of length at most 2 connects identical vertices, adjacent vertices, or vertices with a common neighbor.
- The lower bounds for d(3,2) and d(4,2) rely on the `decide` tactic to exhaustively verify across all 5 vertices that no common neighbor exists between 3 (or 4) and 2.
- The connectivity of the graph and all adjacency checks are verified computationally by Lean's `decide` tactic.
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.
lemma five_vertex_t_star_dist_eq_walk_length_le_two {V : Type*} {G : SimpleGraph V} {u v : V} (p : G.Walk u v) (hp : p.length ≤ 2) : u = v ∨ G.Adj u v ∨ ∃ w, G.Adj u w ∧ G.Adj w v := by cases p with | nil => exact Or.inl rfl | cons h1 q => cases q with | nil => exact Or.inr (Or.inl h1) | cons h2 r => cases r with | nil => exact Or.inr (Or.inr ⟨_, h1, h2⟩) | cons h3 s => simp only [SimpleGraph.Walk.length_cons] at hp omega/-- The six distances in the T-graph that both Wasserstein bounds need. `dist 0 2 = 2` by the triangle inequality through 1 plus non-adjacency; `dist 3 2 = 3` is the only non-trivial one: upper bound by the triangle 3-0-1-2, lower bound because a walk of length at most 2 would give a common neighbour of 3 and 2, and 3's only neighbour is 0 which is not adjacent to 2. -/theorem five_vertex_t_star_dist_eq : five_vertex_t_star.dist 0 1 = 1 ∧ five_vertex_t_star.dist 0 2 = 2 ∧ five_vertex_t_star.dist 3 1 = 2 ∧ five_vertex_t_star.dist 4 1 = 2 ∧ five_vertex_t_star.dist 3 2 = 3 ∧ five_vertex_t_star.dist 4 2 = 3 := by have hconn : five_vertex_t_star.Connected := by decide have d01 : five_vertex_t_star.dist 0 1 = 1 := by rw [SimpleGraph.dist_eq_one_iff_adj] decide have d12 : five_vertex_t_star.dist 1 2 = 1 := by rw [SimpleGraph.dist_eq_one_iff_adj] decide have d30 : five_vertex_t_star.dist 3 0 = 1 := by rw [SimpleGraph.dist_comm, SimpleGraph.dist_eq_one_iff_adj] decide have d40 : five_vertex_t_star.dist 4 0 = 1 := by rw [SimpleGraph.dist_comm, SimpleGraph.dist_eq_one_iff_adj] decide have d02 : five_vertex_t_star.dist 0 2 = 2 := by have hle : five_vertex_t_star.dist 0 2 ≤ 2 := by have := hconn.dist_triangle (u := 0) (v := 1) (w := 2) omega have hlt : 1 < five_vertex_t_star.dist 0 2 := hconn.one_lt_dist_of_ne_of_not_adj (by decide) (by decide) omega have d31 : five_vertex_t_star.dist 3 1 = 2 := by have hle : five_vertex_t_star.dist 3 1 ≤ 2 := by have := hconn.dist_triangle (u := 3) (v := 0) (w := 1) omega have hlt : 1 < five_vertex_t_star.dist 3 1 := hconn.one_lt_dist_of_ne_of_not_adj (by decide) (by decide) omega have d41 : five_vertex_t_star.dist 4 1 = 2 := by have hle : five_vertex_t_star.dist 4 1 ≤ 2 := by have := hconn.dist_triangle (u := 4) (v := 0) (w := 1) omega have hlt : 1 < five_vertex_t_star.dist 4 1 := hconn.one_lt_dist_of_ne_of_not_adj (by decide) (by decide) omega have d32 : five_vertex_t_star.dist 3 2 = 3 := by have hle : five_vertex_t_star.dist 3 2 ≤ 3 := by have := hconn.dist_triangle (u := 3) (v := 0) (w := 2) omega have hgt : ¬ (five_vertex_t_star.dist 3 2 ≤ 2) := by intro hle2 obtain ⟨p, hp⟩ := hconn.exists_walk_length_eq_dist 3 2 have hp2 : p.length ≤ 2 := by omega have hcases := five_vertex_t_star_dist_eq_walk_length_le_two p hp2 revert hcases decide omega have d42 : five_vertex_t_star.dist 4 2 = 3 := by have hle : five_vertex_t_star.dist 4 2 ≤ 3 := by have := hconn.dist_triangle (u := 4) (v := 0) (w := 2) omega have hgt : ¬ (five_vertex_t_star.dist 4 2 ≤ 2) := by intro hle2 obtain ⟨p, hp⟩ := hconn.exists_walk_length_eq_dist 4 2 have hp2 : p.length ≤ 2 := by omega have hcases := five_vertex_t_star_dist_eq_walk_length_le_two p hp2 revert hcases decide omega exact ⟨d01, d02, d31, d41, d32, d42⟩