graph_lly_curvature_of_leaf
If x is a leaf of a finite connected graph whose only neighbour is y, then κ_LLY(x, y) = 2/d_y.
Statement
theorem graph_lly_curvature_of_leaf {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (hG : G.Connected) (x y : V) (hxy : G.Adj x y) (hleaf : ∀ w, G.Adj x w → w = y) : graph_lly_curvature G x y = 2 / (G.degree y : ℝ)
- Source
- Helper for the refutation of OP-165 (arXiv:2610.10559, after Theorem 1.4). The value is the known tree formula 2/d_x + 2/d_y − 2 for d_x = 1.
- Verified
- 10 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 11
- graph_lly_curvature_eq_of_ollivier_eqIf κ_α(x, y) = (1 − α)c for all α in an interval (a, 1), then κ_LLY(x, y) = c.
- graph_wasserstein_dist_le_of_planThe Wasserstein distance is at most the cost of any transport plan.
- graph_wasserstein_dist_ge_of_lipschitzWeak Kantorovich duality: for probability measures μ, ν and any function f with f(a) − f(b) ≤ d(a, b), Σ f μ − Σ f ν ≤ W(μ, ν).
- graph_idle_measure_nonnegμ_x^α is nonnegative for 0 ≤ α ≤ 1.
- graph_idle_measure_sum_eq_oneμ_x^α is a probability measure (total mass 1) when x has a neighbour.
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - graph_wasserstein_distThe Wasserstein distance W(μ, ν) between two measures on the vertices of a finite graph: the infimum, over all transport plans π ≥ 0 with…
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - graph_lly_curvatureThe Lin–Lu–Yau curvature κ_LLY(x, y) = lim_{α → 1⁻} κ_α(x, y)/(1 − α).
- 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_ollivier_curvatureThe α-Ollivier–Ricci curvature κ_α(x, y) = 1 − W(μ_x^α, μ_y^α)/d(x, y).
- Used by 2
- graph_lly_curvature_of_twinsIf x and y are adjacent and have the same neighbours apart from each other, then κ_LLY(x, y) = (d_x + 1)/d_x.
- graph_lly_curvature_pos_of_threeIn a finite connected graph with exactly three vertices x, y, z, every edge xy has positive Lin–Lu–Yau curvature.
The proof, explained
To compute the Lin-Lu-Yau curvature κ_LLY(x, y), it suffices to show that the Ollivier-Ricci curvature satisfies κ_Oll(x, y) = (1 - α)(2 / d_y) for lazy random walk parameters α ∈ (1/2, 1). For such α, the idle measure at x is concentrated on {x, y}, while the idle measure at y distributes mass α at y and (1 - α)/d_y to each of its neighbors. The Wasserstein distance W_1(μ_x, μ_y) is computed exactly using Kantorovich duality: an upper bound is obtained from an explicit transport plan that keeps mass stationary at y and routes the mass from x to match the remainder of μ_y, and a matching lower bound is achieved by testing against the 1-Lipschitz function -f, where f vanishes at x, equals 1 at y, and equals 2 elsewhere. Substituting the resulting distance into the definition of Ollivier-Ricci curvature and taking the limit completes the proof.
The vertex y has strictly positive degree, x has degree 1, x ≠ y, and d(x, y) = 1.
Since x is adjacent to y, y has at least one neighbor, so its degree is strictly positive. As x is a leaf whose only neighbor is y, the neighbor finset of x is the singleton {y}, so the degree of x is 1 by SimpleGraph.card_neighborFinset_eq_degree and Finset.card_singleton. Because x and y are adjacent, they are distinct and at graph distance 1 by SimpleGraph.dist_eq_one_iff_adj.mpr.
uses
SimpleGraph.card_neighborFinset_eq_degree,Finset.card_singleton,SimpleGraph.dist_eq_one_iff_adj.mprhave hDpos : 0 < G.degree y := (G.degree_pos_iff_exists_adj y).mpr ⟨x, hxy.symm⟩ have hDR : (0 : ℝ) < G.degree y := by exact_mod_cast hDpos have hdegx : G.degree x = 1 := by rw [← SimpleGraph.card_neighborFinset_eq_degree] have : G.neighborFinset x = {y} := by ext w; simp only [SimpleGraph.mem_neighborFinset, Finset.mem_singleton] exact ⟨hleaf w, fun h => h ▸ hxy⟩ rw [this, Finset.card_singleton] have hne : x ≠ y := G.ne_of_adj hxy have hdxy : G.dist x y = 1 := SimpleGraph.dist_eq_one_iff_adj.mpr hxy
For the test function f : V → ℝ with f(x) = 0, f(y) = 1, and f(b) = 2 elsewhere, every neighbor b of y satisfies d(x, b) ≤ f(b).
Let f be defined as specified. If b = x, then d(x, x) = 0 ≤ f(x) = 0. The case b = y is impossible because simple graphs contain no self-loops. For any other neighbor b of y, the path x ~ y ~ b provides a walk of length 2 from x to b, which bounds the graph distance d(x, b) ≤ 2 = f(b) by SimpleGraph.dist_le.
uses
SimpleGraph.dist_leset f : V → ℝ := fun b => if b = x then 0 else if b = y then 1 else 2 with hf have hfle : ∀ b, G.Adj y b → (G.dist x b : ℝ) ≤ f b := by intro b hb by_cases hbx : b = x · subst b; simp [hf] by_cases hby : b = y · subst b; exact absurd hb G.irrefl simp only [hf, if_neg hbx, if_neg hby] have : G.dist x b ≤ 2 := by have := SimpleGraph.dist_le (SimpleGraph.Walk.cons hxy (SimpleGraph.Walk.cons hb SimpleGraph.Walk.nil)) simpa using this exact_mod_cast this
The negated function -f is 1-Lipschitz: -f(a) - -f(b) ≤ d(a, b) for all vertices a, b.
If a = b, both sides are zero. If a ≠ b, graph connectedness implies d(a, b) ≥ 1. When a = x: if b = y, the difference is -f(x) - -f(y) = 1 = d(x, y); if b ≠ y, b cannot be adjacent to x, so d(x, b) ≠ 1 by SimpleGraph.dist_eq_one_iff_adj.mp, meaning d(x, b) ≥ 2, which satisfies -f(x) - -f(b) = 2 ≤ d(x, b). When a ≠ x, f takes values in {1, 2}, so -f(a) - -f(b) = f(b) - f(a) ≤ 2 - 1 = 1 ≤ d(a, b).
uses
SimpleGraph.dist_eq_one_iff_adj.mphave hfge : ∀ a b, -f a - -f b ≤ (G.dist a b : ℝ) := by intro a b by_cases hab : a = b · subst hab; simp have h1 : 1 ≤ G.dist a b := hG.pos_dist_of_ne hab have h1' : (1 : ℝ) ≤ G.dist a b := by exact_mod_cast h1 by_cases hax : a = x · subst a by_cases hby : b = y · subst b; simp [hf, hne.symm]; linarith have hbx : b ≠ x := fun h => hab h.symm have hnadj : ¬ G.Adj x b := fun h => hby (hleaf b h) have h2 : 2 ≤ G.dist x b := by have : G.dist x b ≠ 1 := fun h => hnadj (SimpleGraph.dist_eq_one_iff_adj.mp h) omega have h2' : (2 : ℝ) ≤ G.dist x b := by exact_mod_cast h2 simp [hf, hbx, hby]; linarith · simp only [hf, if_neg hax] split_ifs <;> linarith
It suffices to show that for all α ∈ (1/2, 1), the Ollivier-Ricci curvature is κ_Oll(G, α, x, y) = (1 - α) * (2 / d_y).
Lin-Lu-Yau curvature is defined as the limit of κ_Oll / (1 - α) as α → 1⁻. By graph_lly_curvature_eq_of_ollivier_eq, showing that κ_Oll(α) = (1 - α) * c for all α in an interval (1/2, 1) implies that the Lin-Lu-Yau curvature equals c = 2 / d_y.
uses
graph_lly_curvature_eq_of_ollivier_eqapply graph_lly_curvature_eq_of_ollivier_eq G x y _ (1/2) (by norm_num) intro α hα1 hα2
For α ∈ (1/2, 1), the idle measures μ_x and μ_y are probability measures, with μ_x supported on {x, y} and μ_y distributing mass α at y and q = (1 - α)/d_y to each neighbor of y.
Let q = (1 - α) / d_y, which is non-negative by div_nonneg. Unfolding the definition of idle measure, μ_y assigns mass α to y and q to each neighbor of y, while μ_x assigns mass α to x and (1 - α)/d_x = 1 - α to its unique neighbor y. By graph_idle_measure_sum_eq_one, both measures sum to 1.
uses
div_nonneg,graph_idle_measure_sum_eq_oneset q : ℝ := (1 - α) / (G.degree y : ℝ) with hq have hq0 : 0 ≤ q := div_nonneg (by linarith) hDR.le have hμy : ∀ b, graph_idle_measure G α y b = if b = y then α else if G.Adj y b then q else 0 := by intro b; rfl have hμx : ∀ b, graph_idle_measure G α x b = if b = x then α else if b = y then 1 - α else 0 := by intro b unfold graph_idle_measure by_cases hbx : b = x · simp [hbx] by_cases hby : b = y · subst b; simp [hbx, hxy, hdegx] rw [if_neg hbx, if_neg hbx, if_neg hby, if_neg (fun h => hby (hleaf b h))] have hsy : ∑ b, graph_idle_measure G α y b = 1 := graph_idle_measure_sum_eq_one G α y hDpos have hsx : ∑ b, graph_idle_measure G α x b = 1 := graph_idle_measure_sum_eq_one G α x (by omega)
The expectation of f under μ_x is ∑_b f(b) μ_x(b) = 1 - α.
Because μ_x is supported only on x and y, and f(x) = 0 while f(y) = 1, every term in the sum vanishes except at b = y, leaving f(x) μ_x(x) + f(y) μ_x(y) = 0 · α + 1 · (1 - α) = 1 - α.
have Sx : ∑ b, f b * graph_idle_measure G α x b = 1 - α := by have term : ∀ b, f b * graph_idle_measure G α x b = if b = y then 1 - α else 0 := by intro b rw [hμx] by_cases hbx : b = x · subst b; simp [hf, hne] by_cases hby : b = y · subst b; simp [hf, hbx] simp [hf, hbx, hby] simp_rw [term] simp
The expectation of f under μ_y is ∑_b f(b) μ_y(b) = α + 2q(d_y - 1).
The idle measure μ_y assigns mass α to y (where f(y) = 1), mass q to x (where f(x) = 0), and mass q to each of the d_y - 1 other neighbors in N(y) \ {x} (where f(b) = 2). Distributing the sum using Finset.sum_add_distrib and computing the cardinality of N(y) \ {x} as d_y - 1 via Finset.card_erase_of_mem, SimpleGraph.card_neighborFinset_eq_degree, and Nat.cast_sub evaluates the sum to α + 2q(d_y - 1).
uses
Finset.sum_add_distrib,Finset.card_erase_of_mem,SimpleGraph.card_neighborFinset_eq_degree,Nat.cast_subhave Sy : ∑ b, f b * graph_idle_measure G α y b = α + 2 * q * ((G.degree y : ℝ) - 1) := by have term : ∀ b, f b * graph_idle_measure G α y b = (if b = y then α else 0) + (if b ∈ (G.neighborFinset y).erase x then 2 * q else 0) := by intro b rw [hμy] by_cases hbx : b = x · subst b; simp [hf, hne] by_cases hby : b = y · subst b; simp [hf, hbx] simp [hf, hbx, hby, SimpleGraph.mem_neighborFinset] simp_rw [term] rw [Finset.sum_add_distrib] simp only [Finset.sum_ite_eq', Finset.sum_ite_eq, Finset.mem_univ, if_true, Finset.sum_ite_mem, Finset.univ_inter, Finset.sum_const, nsmul_eq_mul] rw [Finset.card_erase_of_mem (by simpa [SimpleGraph.mem_neighborFinset] using hxy.symm), SimpleGraph.card_neighborFinset_eq_degree, Nat.cast_sub (by omega)] push_cast; ring
The Wasserstein distance satisfies the upper bound W_1(μ_x, μ_y) ≤ α + 2q(d_y - 1) - (1 - α).
We construct an explicit coupling π: at a = y, mass 1 - α is sent directly to b = y at zero distance cost; at a = x, the remaining mass of μ_y is supplied (sending α - (1 - α) to y and μ_y(b) to each b ≠ y). By graph_idle_measure_nonneg, π is non-negative, and its marginals equal μ_x and μ_y. By graph_wasserstein_dist_le_of_plan, the Wasserstein distance is bounded by the transport cost ∑_a ∑_b d(a, b) π(a, b). Using Fintype.sum_eq_single, this simplifies to ∑_b d(x, b) μ_y(b) - (1 - α). Using d(x, b) ≤ f(b) together with Finset.sum_le_sum and mul_le_mul_of_nonneg_right, this is at most ∑_b f(b) μ_y(b) - (1 - α) = α + 2q(d_y - 1) - (1 - α).
uses
le_antisymm,graph_idle_measure_nonneg,graph_wasserstein_dist_le_of_plan,Fintype.sum_eq_single,Finset.sum_le_sum,mul_le_mul_of_nonneg_righthave hW : graph_wasserstein_dist G (graph_idle_measure G α x) (graph_idle_measure G α y) = α + 2 * q * ((G.degree y : ℝ) - 1) - (1 - α) := by apply le_antisymm · set π : V → V → ℝ := fun a b => (if a = x then graph_idle_measure G α y b - (if b = y then 1 - α else 0) else 0) + (if a = y then (if b = y then 1 - α else 0) else 0) with hπ have h0 : ∀ a b, 0 ≤ π a b := by intro a b simp only [hπ] have hn := graph_idle_measure_nonneg G α (by linarith) hα2.le y b by_cases hax : a = x · subst a simp only [if_true, if_neg hne, add_zero] by_cases hby : b = y · subst b; rw [hμy]; simp; linarith · simp [hby]; exact hn · split_ifs <;> linarith have hc : ∀ a b, (G.dist a b : ℝ) * π a b = if a = x then (G.dist x b : ℝ) * (graph_idle_measure G α y b - (if b = y then 1 - α else 0)) else 0 := by intro a b simp only [hπ] by_cases hax : a = x · subst a; simp [hne] · by_cases hay : a = y · subst a by_cases hby : b = y · subst b; simp [hax] · simp [hax, hby] · simp [hax, hay] calc graph_wasserstein_dist G _ _ ≤ ∑ a, ∑ b, (G.dist a b : ℝ) * π a b := by apply graph_wasserstein_dist_le_of_plan G _ _ π h0 · intro a simp only [hπ] rw [Finset.sum_add_distrib, Finset.sum_ite_irrel, Finset.sum_ite_irrel, Finset.sum_const_zero, Finset.sum_sub_distrib, hsy] simp only [Finset.sum_ite_eq', Finset.sum_ite_eq, Finset.mem_univ, if_true] rw [hμx] by_cases hax : a = x · subst a; simp [hne] · by_cases hay : a = y · subst a; simp [hax] · simp [hax, hay] · intro b simp only [hπ] rw [Finset.sum_add_distrib] simp only [Finset.sum_ite_eq', Finset.sum_ite_eq, Finset.mem_univ, if_true] ring _ = ∑ b, (G.dist x b : ℝ) * graph_idle_measure G α y b - (1 - α) := by simp_rw [hc] rw [Fintype.sum_eq_single x (fun a ha => by simp [ha])] simp only [if_true, mul_sub, Finset.sum_sub_distrib, mul_ite, mul_zero, Finset.sum_ite_eq', Finset.sum_ite_eq, Finset.mem_univ, hdxy, Nat.cast_one, one_mul] _ ≤ ∑ b, f b * graph_idle_measure G α y b - (1 - α) := by apply sub_le_sub_right apply Finset.sum_le_sum intro b _ rw [hμy] split_ifs with h1 h2 · subst b; simp [hf, hne.symm, hdxy] · exact mul_le_mul_of_nonneg_right (hfle b h2) hq0 · simp _ = _ := by rw [Sy]
The Wasserstein distance satisfies the matching lower bound via Kantorovich duality, establishing W_1(μ_x, μ_y) = α + 2q(d_y - 1) - (1 - α).
By Kantorovich duality (graph_wasserstein_dist_ge_of_lipschitz) and non-negativity of the idle measures (graph_idle_measure_nonneg), testing against the 1-Lipschitz function -f gives W_1(μ_x, μ_y) ≥ ∑_a (-f(a)) μ_x(a) - ∑_b (-f(b)) μ_y(b) = ∑_b f(b) μ_y(b) - ∑_a f(a) μ_x(a) = (α + 2q(d_y - 1)) - (1 - α). Together with the upper bound, antisymmetry yields equality.
uses
graph_wasserstein_dist_ge_of_lipschitz,graph_idle_measure_nonneg· have := graph_wasserstein_dist_ge_of_lipschitz G _ _ (graph_idle_measure_nonneg G α (by linarith) hα2.le x) (graph_idle_measure_nonneg G α (by linarith) hα2.le y) hsx hsy (fun b => -f b) hfge simp only [neg_mul, Finset.sum_neg_distrib] at this rw [Sx, Sy] at this linarith
The Ollivier-Ricci curvature is κ_Oll(G, α, x, y) = (1 - α) * (2 / d_y), concluding the theorem.
By definition, κ_Oll(G, α, x, y) = 1 - W_1(μ_x, μ_y) / d(x, y). Substituting d(x, y) = 1, the formula for W_1, and q = (1 - α) / d_y, algebraic simplification and ring operations yield 1 - (α + 2((1 - α)/d_y)(d_y - 1) - (1 - α)) = (1 - α)(2 / d_y).
unfold graph_ollivier_curvature rw [hW, hdxy, hq] simp only [Nat.cast_one, div_one] field_simp ring
SimpleGraph.card_neighborFinset_eq_degree- The cardinality of the finset of neighbors of a vertex equals its degree.
Finset.card_singleton- A singleton set has cardinality 1.
SimpleGraph.dist_eq_one_iff_adj.mpr- If two vertices in a graph are adjacent, the graph distance between them is 1.
SimpleGraph.dist_le- The graph distance between two vertices is bounded above by the length of any walk between them.
SimpleGraph.dist_eq_one_iff_adj.mp- If the graph distance between two vertices is 1, then they are adjacent.
graph_lly_curvature_eq_of_ollivier_eq- If the Ollivier-Ricci curvature satisfies κ_Oll(α) = (1 - α) * c for all α in an interval (a, 1), then the Lin-Lu-Yau curvature equals c.
div_nonneg- The quotient of two non-negative numbers is non-negative.
graph_idle_measure_sum_eq_one- For any vertex with positive degree, its idle measure sums to 1.
Finset.sum_add_distrib- A sum of terms (f x + g x) over a finite set distributes into the sum of f x plus the sum of g x.
Finset.card_erase_of_mem- Erasing an element from a finite set that contains it decreases the set's cardinality by 1.
Nat.cast_sub- The coercion of a natural number difference n - m to a ring with 1 equals n - m whenever m ≤ n.
le_antisymm- If a ≤ b and b ≤ a in a partial order, then a = b.
graph_idle_measure_nonneg- For 0 ≤ α ≤ 1, the idle measure is non-negative at every vertex.
graph_wasserstein_dist_le_of_plan- The Wasserstein distance between two measures is bounded above by the transport cost of any valid coupling (transport plan).
Fintype.sum_eq_single- A sum over a finite type where every term except one vanishes reduces to that single term.
Finset.sum_le_sum- If f i ≤ g i for all i in a finite set, then the sum of f is at most the sum of g.
mul_le_mul_of_nonneg_right- If b ≤ c and a is non-negative, then b * a ≤ c * a.
graph_wasserstein_dist_ge_of_lipschitz- Kantorovich duality: the Wasserstein distance between probability measures μ and ν is bounded below by ∑ f μ - ∑ f ν for any 1-Lipschitz function f.
- The verification that -f is 1-Lipschitz (lines 44-45) relies on exhaustive case analysis via split_ifs and linear arithmetic (linarith).
- The final step (lines 163-164) closes the Ollivier-Ricci curvature calculation by field simplification (field_simp) and ring automation (ring).
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.
theorem graph_lly_curvature_of_leaf {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (hG : G.Connected) (x y : V) (hxy : G.Adj x y) (hleaf : ∀ w, G.Adj x w → w = y) : graph_lly_curvature G x y = 2 / (G.degree y : ℝ) := by have hDpos : 0 < G.degree y := (G.degree_pos_iff_exists_adj y).mpr ⟨x, hxy.symm⟩ have hDR : (0 : ℝ) < G.degree y := by exact_mod_cast hDpos have hdegx : G.degree x = 1 := by rw [← SimpleGraph.card_neighborFinset_eq_degree] have : G.neighborFinset x = {y} := by ext w; simp only [SimpleGraph.mem_neighborFinset, Finset.mem_singleton] exact ⟨hleaf w, fun h => h ▸ hxy⟩ rw [this, Finset.card_singleton] have hne : x ≠ y := G.ne_of_adj hxy have hdxy : G.dist x y = 1 := SimpleGraph.dist_eq_one_iff_adj.mpr hxy set f : V → ℝ := fun b => if b = x then 0 else if b = y then 1 else 2 with hf have hfle : ∀ b, G.Adj y b → (G.dist x b : ℝ) ≤ f b := by intro b hb by_cases hbx : b = x · subst b; simp [hf] by_cases hby : b = y · subst b; exact absurd hb G.irrefl simp only [hf, if_neg hbx, if_neg hby] have : G.dist x b ≤ 2 := by have := SimpleGraph.dist_le (SimpleGraph.Walk.cons hxy (SimpleGraph.Walk.cons hb SimpleGraph.Walk.nil)) simpa using this exact_mod_cast this have hfge : ∀ a b, -f a - -f b ≤ (G.dist a b : ℝ) := by intro a b by_cases hab : a = b · subst hab; simp have h1 : 1 ≤ G.dist a b := hG.pos_dist_of_ne hab have h1' : (1 : ℝ) ≤ G.dist a b := by exact_mod_cast h1 by_cases hax : a = x · subst a by_cases hby : b = y · subst b; simp [hf, hne.symm]; linarith have hbx : b ≠ x := fun h => hab h.symm have hnadj : ¬ G.Adj x b := fun h => hby (hleaf b h) have h2 : 2 ≤ G.dist x b := by have : G.dist x b ≠ 1 := fun h => hnadj (SimpleGraph.dist_eq_one_iff_adj.mp h) omega have h2' : (2 : ℝ) ≤ G.dist x b := by exact_mod_cast h2 simp [hf, hbx, hby]; linarith · simp only [hf, if_neg hax] split_ifs <;> linarith apply graph_lly_curvature_eq_of_ollivier_eq G x y _ (1/2) (by norm_num) intro α hα1 hα2 set q : ℝ := (1 - α) / (G.degree y : ℝ) with hq have hq0 : 0 ≤ q := div_nonneg (by linarith) hDR.le have hμy : ∀ b, graph_idle_measure G α y b = if b = y then α else if G.Adj y b then q else 0 := by intro b; rfl have hμx : ∀ b, graph_idle_measure G α x b = if b = x then α else if b = y then 1 - α else 0 := by intro b unfold graph_idle_measure by_cases hbx : b = x · simp [hbx] by_cases hby : b = y · subst b; simp [hbx, hxy, hdegx] rw [if_neg hbx, if_neg hbx, if_neg hby, if_neg (fun h => hby (hleaf b h))] have hsy : ∑ b, graph_idle_measure G α y b = 1 := graph_idle_measure_sum_eq_one G α y hDpos have hsx : ∑ b, graph_idle_measure G α x b = 1 := graph_idle_measure_sum_eq_one G α x (by omega) have Sx : ∑ b, f b * graph_idle_measure G α x b = 1 - α := by have term : ∀ b, f b * graph_idle_measure G α x b = if b = y then 1 - α else 0 := by intro b rw [hμx] by_cases hbx : b = x · subst b; simp [hf, hne] by_cases hby : b = y · subst b; simp [hf, hbx] simp [hf, hbx, hby] simp_rw [term] simp have Sy : ∑ b, f b * graph_idle_measure G α y b = α + 2 * q * ((G.degree y : ℝ) - 1) := by have term : ∀ b, f b * graph_idle_measure G α y b = (if b = y then α else 0) + (if b ∈ (G.neighborFinset y).erase x then 2 * q else 0) := by intro b rw [hμy] by_cases hbx : b = x · subst b; simp [hf, hne] by_cases hby : b = y · subst b; simp [hf, hbx] simp [hf, hbx, hby, SimpleGraph.mem_neighborFinset] simp_rw [term] rw [Finset.sum_add_distrib] simp only [Finset.sum_ite_eq', Finset.sum_ite_eq, Finset.mem_univ, if_true, Finset.sum_ite_mem, Finset.univ_inter, Finset.sum_const, nsmul_eq_mul] rw [Finset.card_erase_of_mem (by simpa [SimpleGraph.mem_neighborFinset] using hxy.symm), SimpleGraph.card_neighborFinset_eq_degree, Nat.cast_sub (by omega)] push_cast; ring have hW : graph_wasserstein_dist G (graph_idle_measure G α x) (graph_idle_measure G α y) = α + 2 * q * ((G.degree y : ℝ) - 1) - (1 - α) := by apply le_antisymm · set π : V → V → ℝ := fun a b => (if a = x then graph_idle_measure G α y b - (if b = y then 1 - α else 0) else 0) + (if a = y then (if b = y then 1 - α else 0) else 0) with hπ have h0 : ∀ a b, 0 ≤ π a b := by intro a b simp only [hπ] have hn := graph_idle_measure_nonneg G α (by linarith) hα2.le y b by_cases hax : a = x · subst a simp only [if_true, if_neg hne, add_zero] by_cases hby : b = y · subst b; rw [hμy]; simp; linarith · simp [hby]; exact hn · split_ifs <;> linarith have hc : ∀ a b, (G.dist a b : ℝ) * π a b = if a = x then (G.dist x b : ℝ) * (graph_idle_measure G α y b - (if b = y then 1 - α else 0)) else 0 := by intro a b simp only [hπ] by_cases hax : a = x · subst a; simp [hne] · by_cases hay : a = y · subst a by_cases hby : b = y · subst b; simp [hax] · simp [hax, hby] · simp [hax, hay] calc graph_wasserstein_dist G _ _ ≤ ∑ a, ∑ b, (G.dist a b : ℝ) * π a b := by apply graph_wasserstein_dist_le_of_plan G _ _ π h0 · intro a simp only [hπ] rw [Finset.sum_add_distrib, Finset.sum_ite_irrel, Finset.sum_ite_irrel, Finset.sum_const_zero, Finset.sum_sub_distrib, hsy] simp only [Finset.sum_ite_eq', Finset.sum_ite_eq, Finset.mem_univ, if_true] rw [hμx] by_cases hax : a = x · subst a; simp [hne] · by_cases hay : a = y · subst a; simp [hax] · simp [hax, hay] · intro b simp only [hπ] rw [Finset.sum_add_distrib] simp only [Finset.sum_ite_eq', Finset.sum_ite_eq, Finset.mem_univ, if_true] ring _ = ∑ b, (G.dist x b : ℝ) * graph_idle_measure G α y b - (1 - α) := by simp_rw [hc] rw [Fintype.sum_eq_single x (fun a ha => by simp [ha])] simp only [if_true, mul_sub, Finset.sum_sub_distrib, mul_ite, mul_zero, Finset.sum_ite_eq', Finset.sum_ite_eq, Finset.mem_univ, hdxy, Nat.cast_one, one_mul] _ ≤ ∑ b, f b * graph_idle_measure G α y b - (1 - α) := by apply sub_le_sub_right apply Finset.sum_le_sum intro b _ rw [hμy] split_ifs with h1 h2 · subst b; simp [hf, hne.symm, hdxy] · exact mul_le_mul_of_nonneg_right (hfle b h2) hq0 · simp _ = _ := by rw [Sy] · have := graph_wasserstein_dist_ge_of_lipschitz G _ _ (graph_idle_measure_nonneg G α (by linarith) hα2.le x) (graph_idle_measure_nonneg G α (by linarith) hα2.le y) hsx hsy (fun b => -f b) hfge simp only [neg_mul, Finset.sum_neg_distrib] at this rw [Sx, Sy] at this linarith unfold graph_ollivier_curvature rw [hW, hdxy, hq] simp only [Nat.cast_one, div_one] field_simp ring