graph_lly_curvature_of_twins
If x and y are adjacent and have the same neighbours apart from each other, then κ_LLY(x, y) = (d_x + 1)/d_x.
Statement
theorem graph_lly_curvature_of_twins {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (hG : G.Connected) (x y : V) (hxy : G.Adj x y) (htw : ∀ w, w ≠ x → w ≠ y → (G.Adj x w ↔ G.Adj y w)) : graph_lly_curvature G x y = ((G.degree x : ℝ) + 1) / (G.degree x : ℝ)
- Source
- Helper for the refutation of OP-165 (arXiv:2610.10559, after Theorem 1.4). Generalizes κ_LLY = n/(n−1) on the complete graph K_n.
- Verified
- 10 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 10
- 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.
- graph_wasserstein_distThe Wasserstein distance W(μ, ν) between two measures on the vertices of a finite graph: the infimum, over all transport plans π ≥ 0 with…
- 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_lly_curvature_of_leafIf x is a leaf of a finite connected graph whose only neighbour is y, then κ_LLY(x, y) = 2/d_y.
- graph_ollivier_curvatureThe α-Ollivier–Ricci curvature κ_α(x, y) = 1 − W(μ_x^α, μ_y^α)/d(x, y).
- Used by 1
- 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
The Lin-Lu-Yau curvature κ_LLY(x, y) of an edge between adjacent twin vertices is computed via the limiting behavior of the idle Ollivier curvature κ_α(x, y) as α → 1. Because x and y share all neighbors outside {x, y}, their degrees are equal: d_x = d_y. For idle parameter α ∈ (1/2, 1), the Wasserstein distance W₁(μ_x, μ_y) between the idle measures is shown to be exactly α - q (where q = (1 - α)/d_x) by constructing an explicit coupling for the upper bound and testing against the 1-Lipschitz indicator function 1_{x} for the matching lower bound. Substituting this distance into the definition of Ollivier curvature gives κ_α(x, y) = (1 - α)(d_x + 1)/d_x, which establishes that κ_LLY(x, y) = (d_x + 1)/d_x.
x ≠ y, x is a neighbor of y, and y is a neighbor of x.
Because x and y are adjacent in the simple graph G, they are distinct vertices, and each lies in the finite neighborhood of the other.
uses
SimpleGraph.mem_neighborFinsethave hne : x ≠ y := G.ne_of_adj hxy have hxN : x ∈ G.neighborFinset y := by simpa [SimpleGraph.mem_neighborFinset] using hxy.symm have hyN : y ∈ G.neighborFinset x := by simpa [SimpleGraph.mem_neighborFinset] using hxy
The degrees of x and y are equal: d_y = d_x.
The degree of a vertex is the cardinality of its neighborhood. Removing x from the neighborhood of y and removing y from the neighborhood of x yields the exact same set, since any other vertex is adjacent to x if and only if it is adjacent to y by the twin hypothesis, and no vertex is adjacent to itself. Since x ∈ N(y) and y ∈ N(x), removing them decreases the cardinality of each set by 1. Equality of the punctured neighborhoods then implies |N(y)| = |N(x)|.
uses
SimpleGraph.card_neighborFinset_eq_degree,Finset.mem_erase,SimpleGraph.mem_neighborFinset,Finset.card_erase_of_mem,Finset.card_pos.mprhave hdeg : G.degree y = G.degree x := by rw [← SimpleGraph.card_neighborFinset_eq_degree, ← SimpleGraph.card_neighborFinset_eq_degree] have hs : (G.neighborFinset y).erase x = (G.neighborFinset x).erase y := by ext w; simp only [Finset.mem_erase, SimpleGraph.mem_neighborFinset] constructor · rintro ⟨hwx, hyw⟩ have hwy : w ≠ y := fun h => G.irrefl (h ▸ hyw) exact ⟨hwy, (htw w hwx hwy).mpr hyw⟩ · rintro ⟨hwy, hxw⟩ have hwx : w ≠ x := fun h => G.irrefl (h ▸ hxw) exact ⟨hwx, (htw w hwx hwy).mp hxw⟩ have c1 := Finset.card_erase_of_mem hxN have c2 := Finset.card_erase_of_mem hyN rw [hs] at c1 have p1 : 0 < (G.neighborFinset y).card := Finset.card_pos.mpr ⟨x, hxN⟩ have p2 : 0 < (G.neighborFinset x).card := Finset.card_pos.mpr ⟨y, hyN⟩ omega
The degree of x is strictly positive, and the graph distance dist(x, y) = 1.
Because x is adjacent to y, its degree is at least 1, so d_x > 0 both as a natural number and as a real number. Furthermore, any two adjacent vertices in a simple graph have distance 1.
uses
SimpleGraph.dist_eq_one_iff_adj.mprhave hDpos : 0 < G.degree x := (G.degree_pos_iff_exists_adj x).mpr ⟨y, hxy⟩ have hDR : (0 : ℝ) < G.degree x := by exact_mod_cast hDpos have hdxy : G.dist x y = 1 := SimpleGraph.dist_eq_one_iff_adj.mpr hxy
It suffices to show that for every α ∈ (1/2, 1), the Ollivier curvature satisfies κ_α(x, y) = (1 - α) * ((d_x + 1) / d_x).
By graph_lly_curvature_eq_of_ollivier_eq, if the idle Ollivier curvature satisfies κ_α(x, y) = (1 - α) c on an interval (a, 1) with a < 1, then the Lin-Lu-Yau curvature is c. We choose a = 1/2 and fix an arbitrary α ∈ (1/2, 1).
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
The neighbor weight q = (1 - α) / d_x satisfies 0 ≤ q ≤ 1 - α.
Setting q = (1 - α) / d_x, non-negativity follows from α < 1 and d_x > 0. Since d_x ≥ 1, dividing 1 - α by d_x cannot exceed 1 - α.
uses
div_nonneg,div_le_iff₀set q : ℝ := (1 - α) / (G.degree x : ℝ) with hq have hq0 : 0 ≤ q := div_nonneg (by linarith) hDR.le have hqle : q ≤ 1 - α := by rw [hq, div_le_iff₀ hDR] have : (1 : ℝ) ≤ G.degree x := by exact_mod_cast hDpos nlinarith
The idle measures μ_x and μ_y assign mass α to their base vertex, q to each neighbor, and 0 elsewhere, and each sums to 1.
By definition, μ_x puts mass α at x and divides 1 - α equally among the d_x neighbors of x, so each neighbor gets weight q. Since d_y = d_x, μ_y similarly puts mass α at y and weight q at each neighbor of y. Because both degrees are positive, both measures sum to 1 over the vertex set.
uses
graph_idle_measure,graph_idle_measure_sum_eq_onehave hμx : ∀ b, graph_idle_measure G α x b = if b = x then α else if G.Adj x b then q else 0 := by intro b; rfl 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; simp only [graph_idle_measure, hdeg, hq] have hsx : ∑ b, graph_idle_measure G α x b = 1 := graph_idle_measure_sum_eq_one G α x hDpos have hsy : ∑ b, graph_idle_measure G α y b = 1 := graph_idle_measure_sum_eq_one G α y (by rw [hdeg]; exact hDpos)
The indicator function f = 1_{x} is 1-Lipschitz with respect to graph distance: f(a) - f(b) ≤ dist(a, b) for all vertices a, b.
If a = b, then f(a) - f(b) = 0 ≤ dist(a, a) = 0. If a ≠ b, connectedness ensures dist(a, b) ≥ 1. Since f takes values in {0, 1}, the difference f(a) - f(b) is at most 1, which is at most dist(a, b).
set f : V → ℝ := fun b => if b = x then 1 else 0 with hf 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 := by exact_mod_cast hG.pos_dist_of_ne hab simp only [hf] split_ifs <;> linarith
The Wasserstein distance satisfies W₁(μ_x, μ_y) ≤ α - q.
We apply antisymmetry (le_antisymm) to prove equality of the Wasserstein distance to α - q by two bounds. For the upper bound, we construct an explicit transport plan π(a, b) = 1_{a=x, b=y} (α - q) + 1_{a=b} m(a), where m(a) = q if a = x and μ_x(a) otherwise. This plan is non-negative and its marginals match μ_x and μ_y (using the twin property on non-twin neighbors). Because diagonal pairs a = b contribute distance 0, the only non-zero transport cost is between x and y (at distance 1), giving total cost 1 * (α - q) = α - q. By graph_wasserstein_dist_le_of_plan, this upper bounds W₁(μ_x, μ_y).
uses
le_antisymm,graph_idle_measure_nonneg,graph_wasserstein_dist_le_of_plan,Fintype.sum_eq_singlehave hW : graph_wasserstein_dist G (graph_idle_measure G α x) (graph_idle_measure G α y) = α - q := by apply le_antisymm · set m : V → ℝ := fun a => if a = x then q else graph_idle_measure G α x a with hm set π : V → V → ℝ := fun a b => (if a = x then (if b = y then α - q else 0) else 0) + (if a = b then m a else 0) with hπ have hm0 : ∀ a, 0 ≤ m a := by intro a; simp only [hm]; split_ifs · exact hq0 · exact graph_idle_measure_nonneg G α (by linarith) hα2.le x a have h0 : ∀ a b, 0 ≤ π a b := by intro a b simp only [hπ] have := hm0 a split_ifs <;> linarith have hc : ∀ a b, (G.dist a b : ℝ) * π a b = if a = x then (if b = y then α - q else 0) else 0 := by intro a b simp only [hπ] by_cases hab : a = b · subst hab by_cases hax : a = x · subst a; simp [hne] · simp [hax] · rw [if_neg hab, add_zero] by_cases hax : a = x · subst a by_cases hby : b = y · subst b; simp [hdxy] · simp [hby] · simp [hax] 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_const_zero] simp only [Finset.sum_ite_eq', Finset.sum_ite_eq, Finset.mem_univ, if_true] by_cases hax : a = x · subst a; simp [hm, hμx] · simp [hax, hm] · 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] by_cases hby : b = y · subst b; simp [hm, hμx, hμy, hne.symm, hxy] by_cases hbx : b = x · subst b; simp [hm, hμy, hne, hxy.symm] simp only [if_neg hby, hm, if_neg hbx, zero_add, hμx, hμy] simp only [htw b hbx hby] _ = α - q := by simp_rw [hc] rw [Fintype.sum_eq_single x (fun a ha => by simp [ha])] simp
The Wasserstein distance satisfies W₁(μ_x, μ_y) ≥ α - q, so W₁(μ_x, μ_y) = α - q.
By Kantorovich duality (graph_wasserstein_dist_ge_of_lipschitz), the 1-Lipschitz test function f = 1_{x} bounds W₁(μ_x, μ_y) from below by ∑ f μ_x - ∑ f μ_y. The expectation of f under μ_x is μ_x(x) = α, and under μ_y it is μ_y(x) = q (since x is adjacent to y). Their difference is α - q, proving the lower bound and completing the equality W₁(μ_x, μ_y) = α - q.
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 f hfge have e1 : ∑ a, f a * graph_idle_measure G α x a = α := by simp only [hf, ite_mul, one_mul, zero_mul] simp [hμx] have e2 : ∑ a, f a * graph_idle_measure G α y a = q := by simp only [hf, ite_mul, one_mul, zero_mul] simp [hμy, hne, hxy.symm] rw [e1, e2] at this exact this
The Ollivier curvature is κ_α(x, y) = (1 - α) * ((d_x + 1) / d_x), completing the proof.
Unfolding Ollivier curvature, κ_α(x, y) = 1 - W₁(μ_x, μ_y) / dist(x, y). Substituting W₁ = α - q, dist(x, y) = 1, and q = (1 - α) / d_x yields 1 - (α - q) = (1 - α) + (1 - α) / d_x = (1 - α) * ((d_x + 1) / d_x). Clearing denominators and simplifying completes the argument.
uses
graph_ollivier_curvatureunfold graph_ollivier_curvature rw [hW, hdxy, hq] simp only [Nat.cast_one, div_one] field_simp ring
div_le_iff₀- For a non-zero denominator, b / c ≤ a if and only if b ≤ a * c.
div_nonneg- The quotient of two non-negative real numbers is non-negative.
Finset.card_erase_of_mem- Erasing an element from a finite set in which it is present decreases the cardinality by 1.
Finset.card_pos.mpr- A finite set containing at least one element has strictly positive cardinality.
Finset.mem_erase- An element belongs to s \ {b} if and only if it is in s and not equal to b.
Fintype.sum_eq_single- If a function on a finite type vanishes outside a single element a, its total sum equals f(a).
graph_idle_measure- The α-idle measure at a vertex x puts mass α on x, distributes 1 - α uniformly with weight (1 - α)/d_x across all neighbors of x, and is 0 elsewhere.
graph_idle_measure_nonneg- For α in [0, 1], the idle measure takes non-negative values at all vertices.
graph_idle_measure_sum_eq_one- If a vertex x has positive degree, its idle measure sums to 1.
graph_lly_curvature_eq_of_ollivier_eq- If the idle Ollivier curvature satisfies κ_α(x, y) = (1 - α)c for all α in an interval (a, 1), then the Lin-Lu-Yau curvature equals c.
graph_ollivier_curvature- The α-idle Ollivier curvature of an edge (x, y) is 1 - W₁(μ_x, μ_y) / dist(x, y).
graph_wasserstein_dist_ge_of_lipschitz- The Wasserstein distance between two probability measures is bounded below by the difference in their expectations for any 1-Lipschitz test function.
graph_wasserstein_dist_le_of_plan- The Wasserstein distance between two measures is bounded above by the transport cost of any valid coupling whose marginals match those measures.
le_antisymm- If a ≤ b and b ≤ a, then a = b.
SimpleGraph.card_neighborFinset_eq_degree- The cardinality of the neighbor finset of a vertex equals its degree.
SimpleGraph.dist_eq_one_iff_adj.mpr- Two vertices in a graph are at graph distance 1 if and only if they are adjacent.
SimpleGraph.mem_neighborFinset- A vertex belongs to the neighbor finset of v if and only if it is adjacent to v.
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_twins {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (hG : G.Connected) (x y : V) (hxy : G.Adj x y) (htw : ∀ w, w ≠ x → w ≠ y → (G.Adj x w ↔ G.Adj y w)) : graph_lly_curvature G x y = ((G.degree x : ℝ) + 1) / (G.degree x : ℝ) := by have hne : x ≠ y := G.ne_of_adj hxy have hxN : x ∈ G.neighborFinset y := by simpa [SimpleGraph.mem_neighborFinset] using hxy.symm have hyN : y ∈ G.neighborFinset x := by simpa [SimpleGraph.mem_neighborFinset] using hxy have hdeg : G.degree y = G.degree x := by rw [← SimpleGraph.card_neighborFinset_eq_degree, ← SimpleGraph.card_neighborFinset_eq_degree] have hs : (G.neighborFinset y).erase x = (G.neighborFinset x).erase y := by ext w; simp only [Finset.mem_erase, SimpleGraph.mem_neighborFinset] constructor · rintro ⟨hwx, hyw⟩ have hwy : w ≠ y := fun h => G.irrefl (h ▸ hyw) exact ⟨hwy, (htw w hwx hwy).mpr hyw⟩ · rintro ⟨hwy, hxw⟩ have hwx : w ≠ x := fun h => G.irrefl (h ▸ hxw) exact ⟨hwx, (htw w hwx hwy).mp hxw⟩ have c1 := Finset.card_erase_of_mem hxN have c2 := Finset.card_erase_of_mem hyN rw [hs] at c1 have p1 : 0 < (G.neighborFinset y).card := Finset.card_pos.mpr ⟨x, hxN⟩ have p2 : 0 < (G.neighborFinset x).card := Finset.card_pos.mpr ⟨y, hyN⟩ omega have hDpos : 0 < G.degree x := (G.degree_pos_iff_exists_adj x).mpr ⟨y, hxy⟩ have hDR : (0 : ℝ) < G.degree x := by exact_mod_cast hDpos have hdxy : G.dist x y = 1 := SimpleGraph.dist_eq_one_iff_adj.mpr hxy 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 x : ℝ) with hq have hq0 : 0 ≤ q := div_nonneg (by linarith) hDR.le have hqle : q ≤ 1 - α := by rw [hq, div_le_iff₀ hDR] have : (1 : ℝ) ≤ G.degree x := by exact_mod_cast hDpos nlinarith have hμx : ∀ b, graph_idle_measure G α x b = if b = x then α else if G.Adj x b then q else 0 := by intro b; rfl 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; simp only [graph_idle_measure, hdeg, hq] have hsx : ∑ b, graph_idle_measure G α x b = 1 := graph_idle_measure_sum_eq_one G α x hDpos have hsy : ∑ b, graph_idle_measure G α y b = 1 := graph_idle_measure_sum_eq_one G α y (by rw [hdeg]; exact hDpos) set f : V → ℝ := fun b => if b = x then 1 else 0 with hf 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 := by exact_mod_cast hG.pos_dist_of_ne hab simp only [hf] split_ifs <;> linarith have hW : graph_wasserstein_dist G (graph_idle_measure G α x) (graph_idle_measure G α y) = α - q := by apply le_antisymm · set m : V → ℝ := fun a => if a = x then q else graph_idle_measure G α x a with hm set π : V → V → ℝ := fun a b => (if a = x then (if b = y then α - q else 0) else 0) + (if a = b then m a else 0) with hπ have hm0 : ∀ a, 0 ≤ m a := by intro a; simp only [hm]; split_ifs · exact hq0 · exact graph_idle_measure_nonneg G α (by linarith) hα2.le x a have h0 : ∀ a b, 0 ≤ π a b := by intro a b simp only [hπ] have := hm0 a split_ifs <;> linarith have hc : ∀ a b, (G.dist a b : ℝ) * π a b = if a = x then (if b = y then α - q else 0) else 0 := by intro a b simp only [hπ] by_cases hab : a = b · subst hab by_cases hax : a = x · subst a; simp [hne] · simp [hax] · rw [if_neg hab, add_zero] by_cases hax : a = x · subst a by_cases hby : b = y · subst b; simp [hdxy] · simp [hby] · simp [hax] 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_const_zero] simp only [Finset.sum_ite_eq', Finset.sum_ite_eq, Finset.mem_univ, if_true] by_cases hax : a = x · subst a; simp [hm, hμx] · simp [hax, hm] · 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] by_cases hby : b = y · subst b; simp [hm, hμx, hμy, hne.symm, hxy] by_cases hbx : b = x · subst b; simp [hm, hμy, hne, hxy.symm] simp only [if_neg hby, hm, if_neg hbx, zero_add, hμx, hμy] simp only [htw b hbx hby] _ = α - q := by simp_rw [hc] rw [Fintype.sum_eq_single x (fun a ha => by simp [ha])] simp · 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 f hfge have e1 : ∑ a, f a * graph_idle_measure G α x a = α := by simp only [hf, ite_mul, one_mul, zero_mul] simp [hμx] have e2 : ∑ a, f a * graph_idle_measure G α y a = q := by simp only [hf, ite_mul, one_mul, zero_mul] simp [hμy, hne, hxy.symm] rw [e1, e2] at this exact this unfold graph_ollivier_curvature rw [hW, hdxy, hq] simp only [Nat.cast_one, div_one] field_simp ring