lly_curvature_pos_of_edge_connectivity_ge
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
- graph_lly_curvatureThe Lin–Lu–Yau curvature κ_LLY(x, y) = lim_{α → 1⁻} κ_α(x, y)/(1 − α).
- graph_edge_connectivityThe edge-connectivity κ'(G): the largest k such that removing fewer than k edges never disconnects G (0 for a disconnected graph; 0 also…
- graph_lly_curvature_pos_of_wasserstein_lt_oneIf the Wasserstein distance between the lazy random-walk measures μ_x^α and μ_y^α on an edge xy is strictly less than 1 for some α ∈ (0,…
- ediam_le_two_of_minDegree_ge_two_thirdsIf a finite connected graph G on at least two vertices has minimum degree δ(G) ≥ 2n/3 − 1, then its diameter is at most 2.
- exists_idle_measure_wasserstein_dist_lt_one_of_ediam_le_two_and_minDegree_geIn a connected graph of diameter at most 2 with minimum degree at least 2n/3 − 1, for every edge xy there exists α ∈ (0, 1) such that the…
- graph_edge_connectivity_le_minDegreeEdge-connectivity is at most the minimum degree, κ'(G) ≤ δ(G) (for at least two vertices).
- 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_wasserstein_distThe Wasserstein distance W(μ, ν) between two measures on the vertices of a finite graph: the infimum, over all transport plans π ≥ 0 with…
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.
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.
have : Nontrivial V := ⟨x, y, hxy.ne⟩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.
uses
graph_edge_connectivity_le_minDegree,le_transhave 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
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).
uses
ediam_le_two_of_minDegree_ge_two_thirdshave hdiam : G.ediam ≤ 2 := ediam_le_two_of_minDegree_ge_two_thirds G hG hδ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.
uses
exists_idle_measure_wasserstein_dist_lt_one_of_ediam_le_two_and_minDegree_geobtain ⟨α, 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 hxyThe 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.
uses
graph_lly_curvature_pos_of_wasserstein_lt_oneexact 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
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 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