AFTD Auto-Formalizing Theoretical Domains

graph_lly_curvature_of_twins

theoremverified

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
Used by 1

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.

  1. 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.

    lines 5–7

    uses SimpleGraph.mem_neighborFinset

      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
  2. 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)|.

    lines 8–24

    uses SimpleGraph.card_neighborFinset_eq_degree, Finset.mem_erase, SimpleGraph.mem_neighborFinset, Finset.card_erase_of_mem, Finset.card_pos.mpr

      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
  3. 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.

    lines 25–27

    uses SimpleGraph.dist_eq_one_iff_adj.mpr

      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
  4. 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).

    lines 28–29

    uses graph_lly_curvature_eq_of_ollivier_eq

      apply graph_lly_curvature_eq_of_ollivier_eq G x y _ (1/2) (by norm_num)
      intro α hα1 hα2
  5. 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 - α.

    lines 30–35

    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
  6. 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.

    lines 36–42

    uses graph_idle_measure, graph_idle_measure_sum_eq_one

      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)
  7. 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).

    lines 43–50

      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
  8. 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).

    lines 51–104

    uses le_antisymm, graph_idle_measure_nonneg, graph_wasserstein_dist_le_of_plan, Fintype.sum_eq_single

      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
  9. 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.

    lines 105–115

    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
  10. 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.

    lines 116–120

    uses graph_ollivier_curvature

      unfold 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

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
See it in the graphDiscuss this resultChallenge it