AFTD Auto-Formalizing Theoretical Domains

lly_curvature_pos_of_edge_connectivity_ge

theoremverifiedformalization

If a finite connected graph on n vertices has edge-connectivity κ'(G) ≥ 2n/3 − 1, then every edge xy has κ_LLY(x, y) > 0.

Statement

theorem lly_curvature_pos_of_edge_connectivity_ge
    {V : Type} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj]
    (hG : G.Connected)
    (hk : (2 * (Fintype.card V : ℝ)) / 3 - 1 ≤ (graph_edge_connectivity G : ℝ))
    (x y : V) (hxy : G.Adj x y) : 0 < graph_lly_curvature G x y
Formalizes
arXiv:2610.10559 (Edge-Connectivity versus Lin--Lu--Yau Curvature), Theorem 1.3. Gives c(n) ≤ ⌈2n/3 − 1⌉ in OP-165.
Verified
18 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 8

The proof, explained

The proof establishes that the graph's minimum degree satisfies δ(G) ≥ 2n/3 − 1, using the fact that edge-connectivity is always at most minimum degree. This degree bound implies that the graph diameter is at most 2. Together, the diameter and degree bounds ensure the existence of an idleness parameter α ∈ (0, 1) whose idle random walk measures have Wasserstein distance strictly less than 1 across the edge xy. Finally, having Wasserstein distance less than 1 guarantees that the Lin–Lu–Yau curvature on that edge is strictly positive.

  1. The vertex set V is nontrivial (contains at least two distinct elements).

    Because vertices x and y are adjacent, they are distinct (x ≠ y), which witnesses that V has at least two elements.

    line 6

      have : Nontrivial V := ⟨x, y, hxy.ne⟩
  2. The minimum degree of G satisfies δ(G) ≥ 2n/3 − 1.

    The edge-connectivity of any graph is bounded above by its minimum degree (graph_edge_connectivity_le_minDegree). Combining this with the hypothesis 2n/3 − 1 ≤ κ'(G) by transitivity of inequality (le_trans) establishes the lower bound on the minimum degree.

    lines 7–10

    uses graph_edge_connectivity_le_minDegree, le_trans

      have hδ : (2 * (Fintype.card V : ℝ)) / 3 - 1 ≤ (G.minDegree : ℝ) := by
        have h_le : (graph_edge_connectivity G : ℝ) ≤ (G.minDegree : ℝ) := by
          exact_mod_cast (graph_edge_connectivity_le_minDegree G)
        exact le_trans hk h_le
  3. The diameter of G is at most 2.

    In any connected finite graph whose minimum degree satisfies δ(G) ≥ 2n/3 − 1, the graph diameter is at most 2 (ediam_le_two_of_minDegree_ge_two_thirds).

    line 11

    uses ediam_le_two_of_minDegree_ge_two_thirds

      have hdiam : G.ediam ≤ 2 := ediam_le_two_of_minDegree_ge_two_thirds G hG hδ
  4. There exists an idleness parameter α ∈ (0, 1) such that the Wasserstein distance between the idle measures at x and y is strictly less than 1.

    Using the diameter bound diam(G) ≤ 2 and the minimum degree bound δ(G) ≥ 2n/3 − 1, exists_idle_measure_wasserstein_dist_lt_one_of_ediam_le_two_and_minDegree_ge yields an idleness parameter α ∈ (0, 1) for which W₁(μ_x^α, μ_y^α) < 1.

    line 12

    uses exists_idle_measure_wasserstein_dist_lt_one_of_ediam_le_two_and_minDegree_ge

      obtain ⟨α, hα0, hα1, hW⟩ := exists_idle_measure_wasserstein_dist_lt_one_of_ediam_le_two_and_minDegree_ge G hG hdiam hδ x y hxy
  5. The Lin–Lu–Yau curvature along the edge xy is strictly positive.

    By graph_lly_curvature_pos_of_wasserstein_lt_one, having Wasserstein distance strictly less than 1 between the idle measures for some parameter α ∈ (0, 1) implies that the Lin–Lu–Yau curvature κ_LLY(x, y) is strictly positive.

    line 13

    uses graph_lly_curvature_pos_of_wasserstein_lt_one

      exact graph_lly_curvature_pos_of_wasserstein_lt_one G hG x y hxy α hα0 hα1 hW
graph_edge_connectivity_le_minDegree
In any nontrivial finite graph, the edge-connectivity is at most the minimum degree.
le_trans
Inequality is transitive: if a ≤ b and b ≤ c, then a ≤ c.
ediam_le_two_of_minDegree_ge_two_thirds
In a nontrivial connected finite graph on n vertices, if the minimum degree is at least 2n/3 − 1, then the diameter of the graph is at most 2.
exists_idle_measure_wasserstein_dist_lt_one_of_ediam_le_two_and_minDegree_ge
For any edge in a connected finite graph with diameter at most 2 and minimum degree at least 2n/3 − 1, there exists an idleness parameter α ∈ (0, 1) such that the L¹ Wasserstein distance between the idle random walk measures at the endpoints is strictly less than 1.
graph_lly_curvature_pos_of_wasserstein_lt_one
For adjacent vertices x and y in a connected finite graph, if there is an idleness parameter α ∈ (0, 1) with Wasserstein distance W₁(μ_x^α, μ_y^α) < 1, then the Lin–Lu–Yau curvature κ_LLY(x, y) is strictly positive.

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 lly_curvature_pos_of_edge_connectivity_ge    {V : Type} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj]    (hG : G.Connected)    (hk : (2 * (Fintype.card V : ℝ)) / 3 - 1 ≤ (graph_edge_connectivity G : ℝ))    (x y : V) (hxy : G.Adj x y) : 0 < graph_lly_curvature G x y := by  have : Nontrivial V := ⟨x, y, hxy.ne⟩  have hδ : (2 * (Fintype.card V : ℝ)) / 3 - 1 ≤ (G.minDegree : ℝ) := by    have h_le : (graph_edge_connectivity G : ℝ) ≤ (G.minDegree : ℝ) := by      exact_mod_cast (graph_edge_connectivity_le_minDegree G)    exact le_trans hk h_le  have hdiam : G.ediam ≤ 2 := ediam_le_two_of_minDegree_ge_two_thirds G hG hδ  obtain ⟨α, hα0, hα1, hW⟩ := exists_idle_measure_wasserstein_dist_lt_one_of_ediam_le_two_and_minDegree_ge G hG hdiam hδ x y hxy  exact graph_lly_curvature_pos_of_wasserstein_lt_one G hG x y hxy α hα0 hα1 hW
See it in the graphDiscuss this resultChallenge it