five_vertex_min_degree_two_wasserstein_lt_one
Every connected graph on 5 vertices with minimum degree at least 2 has, for each edge xy, some α ∈ (0, 1) with W(μ_x^α, μ_y^α) < 1.
Statement
theorem five_vertex_min_degree_two_wasserstein_lt_one {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (hcard : Fintype.card V = 5) (hG : G.Connected) (hδ : 2 ≤ G.minDegree) (x y : V) (hxy : G.Adj x y) : ∃ α : ℝ, 0 < α ∧ α < 1 ∧ graph_wasserstein_dist G (graph_idle_measure G α x) (graph_idle_measure G α y) < 1
- Source
- step towards lly_positive_edge_connectivity_threshold_five
- Verified
- 18 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 8
- five_vertex_min_degree_two_ediam_le_twoEvery graph on 5 vertices with minimum degree at least 2 has diameter at most 2, hence is connected.
- graph_wasserstein_dist_le_of_planThe Wasserstein distance is at most the cost of any transport plan.
- graph_idle_measureThe lazy random-walk measure μ_x^α at x with idleness α: mass α at x, (1 − α)/d_x at each neighbour of x, 0 elsewhere.
- graph_idle_measure_sum_eq_oneμ_x^α is a probability measure (total mass 1) when x has a neighbour.
- graph_idle_measure_nonnegμ_x^α is nonnegative for 0 ≤ α ≤ 1.
- wasserstein_dist_le_of_diameter_twoOn any graph of diameter at most 2, the Wasserstein distance between probability measures μ and ν with d(x, y) = 1 is bounded by 2 - 2 *…
- five_vertex_min_degree_two_idle_coupling_boundIn any 5-vertex graph with minimum degree at least 2 and adjacent vertices x and y, the idle measures at α = 1/2 satisfy 1 < 2 S0 + m_xy.
- graph_wasserstein_distThe Wasserstein distance W(μ, ν) between two measures on the vertices of a finite graph: the infimum, over all transport plans π ≥ 0 with…
- Used by 2
- lly_five_vertex_pos_of_min_degree_twoEvery connected graph on 5 vertices with minimum degree at least 2 has positive Lin–Lu–Yau curvature on every edge.
- 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…
The proof, explained
To show that every edge $xy$ admits some laziness parameter $\alpha \in (0,1)$ with $W(\mu_x^\alpha, \mu_y^\alpha) < 1$, the proof fixes $\alpha = 1/2$. On any 5-vertex graph with minimum degree at least 2, the diameter is at most 2, allowing the Wasserstein distance between probability measures on an edge to be bounded by $2 - 2S_0 - m_{xy}$, where $S_0$ is the shared probability mass and $m_{xy}$ is the unshared mass at the endpoints. A combinatorial bound specialized to 5-vertex graphs with $\delta \ge 2$ guarantees that $2S_0 + m_{xy} > 1$, which immediately implies $W(\mu_x^{1/2}, \mu_y^{1/2}) < 1$.
It suffices to show that for the choice $\alpha = 1/2$, the Wasserstein distance between the lazy walk measures is strictly less than 1.
The theorem asserts the existence of $\alpha \in (0, 1)$ such that $W(\mu_x^\alpha, \mu_y^\alpha) < 1$. The proof fixes $\alpha = 1/2$, checks $0 < 1/2$ and $1/2 < 1$ by numerical evaluation (`norm_num`), leaving the distance bound as the remaining goal.
have _ := hG use 1 / 2 refine ⟨by norm_num, by norm_num, ?_⟩
The degrees of $x$ and $y$ are strictly positive.
Because the minimum degree $\delta$ of $G$ is at least 2, and the degree of every vertex is at least the minimum degree (`G.minDegree_le_degree`), both $\deg(x)$ and $\deg(y)$ are at least 2, hence strictly positive by linear integer arithmetic (`omega`).
uses
G.minDegree_le_degreehave hdeg_x : 0 < G.degree x := by have := G.minDegree_le_degree x omega have hdeg_y : 0 < G.degree y := by have := G.minDegree_le_degree y omega
The lazy walk measures $\mu_x^{1/2}$ and $\mu_y^{1/2}$ are probability distributions on $V$.
Since $0 \le 1/2 \le 1$, `graph_idle_measure_nonneg` ensures that both measures take non-negative values at every vertex. Since $\deg(x) > 0$ and $\deg(y) > 0$, `graph_idle_measure_sum_eq_one` shows that the probabilities of each measure sum to 1.
uses
graph_idle_measure_nonneg,graph_idle_measure_sum_eq_onehave hμ_nonneg : ∀ a, 0 ≤ graph_idle_measure G (1 / 2) x a := by intro a exact graph_idle_measure_nonneg G (1 / 2) (by norm_num) (by norm_num) x a have hν_nonneg : ∀ b, 0 ≤ graph_idle_measure G (1 / 2) y b := by intro b exact graph_idle_measure_nonneg G (1 / 2) (by norm_num) (by norm_num) y b have hμ_sum : ∑ a, graph_idle_measure G (1 / 2) x a = 1 := graph_idle_measure_sum_eq_one G (1 / 2) x hdeg_x have hν_sum : ∑ b, graph_idle_measure G (1 / 2) y b = 1 := graph_idle_measure_sum_eq_one G (1 / 2) y hdeg_y
The graph has diameter at most 2, so all pairwise distances are at most 2.
By `five_vertex_min_degree_two_ediam_le_two`, any 5-vertex graph with minimum degree at least 2 has extended diameter at most 2. For any pair of vertices $a, b \in V$, the extended distance between them is bounded by the diameter (`SimpleGraph.edist_le_ediam`). Using `le_trans`, `ENat.toNat_le_of_le_natCast`, and `Nat.cast_le.mpr`, this converts to the real inequality $\operatorname{dist}(a, b) \le 2$.
uses
five_vertex_min_degree_two_ediam_le_two,SimpleGraph.edist_le_ediam,le_trans,ENat.toNat_le_of_le_natCast,Nat.cast_le.mprhave hediam : G.ediam ≤ 2 := five_vertex_min_degree_two_ediam_le_two G hcard hδ have hdist2 : ∀ a b : V, (G.dist a b : ℝ) ≤ 2 := by intro a b have hle : G.edist a b ≤ 2 := le_trans SimpleGraph.edist_le_ediam hediam have hnat : G.dist a b ≤ 2 := ENat.toNat_le_of_le_natCast hle exact Nat.cast_le.mpr hnat
The distance between the adjacent vertices $x$ and $y$ is 1.
Because $x$ and $y$ are adjacent, the graph distance $\operatorname{dist}(x, y)$ equals 1 by `G.dist_eq_one_iff_adj.mpr`.
uses
G.dist_eq_one_iff_adj.mprhave hxy_dist : (G.dist x y : ℝ) = 1 := by rw [G.dist_eq_one_iff_adj.mpr hxy] norm_num
The Wasserstein distance satisfies $W(\mu_x^{1/2}, \mu_y^{1/2}) \le 2 - 2S_0 - m_{xy}$.
Applying `wasserstein_dist_le_of_diameter_two` using the verified probability measure properties and the diameter-2 bound yields the coupling upper bound $W(\mu_x^{1/2}, \mu_y^{1/2}) \le 2 - 2S_0 - m_{xy}$, where $S_0$ is the total overlapping mass $\sum_v \min(\mu_x^{1/2}(v), \mu_y^{1/2}(v))$ and $m_{xy} = \min(\mu_1(x), \nu_1(y))$ is the unshared mass at the edge endpoints.
uses
wasserstein_dist_le_of_diameter_twohave h_bound := wasserstein_dist_le_of_diameter_two G hdist2 (graph_idle_measure G (1 / 2) x) (graph_idle_measure G (1 / 2) y) hμ_nonneg hν_nonneg hμ_sum hν_sum x y hxy_distThe Wasserstein distance $W(\mu_x^{1/2}, \mu_y^{1/2})$ is strictly less than 1.
The combinatorial lemma `five_vertex_min_degree_two_idle_coupling_bound` establishes that $1 < 2S_0 + m_{xy}$. Linear arithmetic (`linarith`) combines this with the coupling upper bound $W(\mu_x^{1/2}, \mu_y^{1/2}) \le 2 - (2S_0 + m_{xy})$ to conclude $W(\mu_x^{1/2}, \mu_y^{1/2}) < 1$.
uses
five_vertex_min_degree_two_idle_coupling_boundhave h_comb := five_vertex_min_degree_two_idle_coupling_bound G hcard hδ x y hxy linarith
G.minDegree_le_degree- In any graph, the degree of each vertex is bounded below by the minimum degree.
G.dist_eq_one_iff_adj.mpr- If two vertices in a simple graph are adjacent, the graph distance between them is 1.
SimpleGraph.edist_le_ediam- The extended distance between any pair of vertices is at most the extended diameter of the graph.
le_trans- The ordering relation $\le$ is transitive ($a \le b$ and $b \le c$ imply $a \le c$).
ENat.toNat_le_of_le_natCast- If an extended natural number $m \le n$ (with $n \in \mathbb{N}$), then $m$ converts to a natural number satisfying $m.\mathrm{toNat} \le n$.
Nat.cast_le.mpr- An inequality $m \le n$ between natural numbers implies the corresponding inequality $\uparrow m \le \uparrow n$ in the real numbers.
graph_idle_measure_nonneg- For any parameter $\alpha \in [0, 1]$, the lazy walk measure $\mu_x^\alpha$ takes non-negative values on all vertices.
graph_idle_measure_sum_eq_one- When a vertex $x$ has strictly positive degree, its lazy walk measure $\mu_x^\alpha$ sums to 1 over all vertices.
five_vertex_min_degree_two_ediam_le_two- Every simple graph on 5 vertices with minimum degree at least 2 has extended diameter at most 2.
wasserstein_dist_le_of_diameter_two- On a graph of diameter at most 2, the Wasserstein distance between probability measures $\mu$ and $\nu$ on an edge $xy$ is at most $2 - 2S_0 - m_{xy}$, where $S_0$ is the total overlapping mass and $m_{xy}$ is the minimum unshared mass at $x$ and $y$.
five_vertex_min_degree_two_idle_coupling_bound- In any 5-vertex graph with minimum degree at least 2, the idle measures with $\alpha = 1/2$ at adjacent vertices satisfy $2S_0 + m_{xy} > 1$.
- The connectedness hypothesis `hG` is brought into scope at line 7 with `have _ := hG` but is not actively used; the minimum degree condition $\delta \ge 2$ on 5 vertices already ensures diameter at most 2 and hence connectedness.
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.
/-- The geometric core of part (i): on 5 vertices with δ ≥ 2, every edge admits some α ∈ (0,1) where the two lazy measures are closer than 1 in W. Uses δ ≥ 2 = (n−1)/2 hence ediam ≤ 2, so all non-neighbour pairs are at distance exactly 2. -/theorem five_vertex_min_degree_two_wasserstein_lt_one {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (hcard : Fintype.card V = 5) (hG : G.Connected) (hδ : 2 ≤ G.minDegree) (x y : V) (hxy : G.Adj x y) : ∃ α : ℝ, 0 < α ∧ α < 1 ∧ graph_wasserstein_dist G (graph_idle_measure G α x) (graph_idle_measure G α y) < 1 := by have _ := hG use 1 / 2 refine ⟨by norm_num, by norm_num, ?_⟩ have hdeg_x : 0 < G.degree x := by have := G.minDegree_le_degree x omega have hdeg_y : 0 < G.degree y := by have := G.minDegree_le_degree y omega have hμ_nonneg : ∀ a, 0 ≤ graph_idle_measure G (1 / 2) x a := by intro a exact graph_idle_measure_nonneg G (1 / 2) (by norm_num) (by norm_num) x a have hν_nonneg : ∀ b, 0 ≤ graph_idle_measure G (1 / 2) y b := by intro b exact graph_idle_measure_nonneg G (1 / 2) (by norm_num) (by norm_num) y b have hμ_sum : ∑ a, graph_idle_measure G (1 / 2) x a = 1 := graph_idle_measure_sum_eq_one G (1 / 2) x hdeg_x have hν_sum : ∑ b, graph_idle_measure G (1 / 2) y b = 1 := graph_idle_measure_sum_eq_one G (1 / 2) y hdeg_y have hediam : G.ediam ≤ 2 := five_vertex_min_degree_two_ediam_le_two G hcard hδ have hdist2 : ∀ a b : V, (G.dist a b : ℝ) ≤ 2 := by intro a b have hle : G.edist a b ≤ 2 := le_trans SimpleGraph.edist_le_ediam hediam have hnat : G.dist a b ≤ 2 := ENat.toNat_le_of_le_natCast hle exact Nat.cast_le.mpr hnat have hxy_dist : (G.dist x y : ℝ) = 1 := by rw [G.dist_eq_one_iff_adj.mpr hxy] norm_num have h_bound := wasserstein_dist_le_of_diameter_two G hdist2 (graph_idle_measure G (1 / 2) x) (graph_idle_measure G (1 / 2) y) hμ_nonneg hν_nonneg hμ_sum hν_sum x y hxy_dist have h_comb := five_vertex_min_degree_two_idle_coupling_bound G hcard hδ x y hxy linarith