edge_connectivity_ge_min_degree_mul_lly_lower_bound_two
Every finite connected graph of diameter 2 has κ'(G) ≥ δ(G) · κ_LLY^(2)(G).
Statement
theorem edge_connectivity_ge_min_degree_mul_lly_lower_bound_two {V : Type} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (hG : G.Connected) (hd : G.diam = 2) : (G.minDegree : ℝ) * graph_lly_curvature_lower_bound G 2 ≤ (graph_edge_connectivity G : ℝ)
- Formalizes
- arXiv:2610.10559 (Edge-Connectivity versus Lin--Lu--Yau Curvature), Theorem 1.1 (for finite graphs).
- Verified
- 18 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- graph_lly_curvature_lower_boundThe lower Lin–Lu–Yau curvature bound at scale i: κ_LLY^(i)(G) = inf { κ_LLY(x, y) : d(x, y) = i }.
- 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_lower_bound_two_le_oneFor every finite connected graph G, the lower Lin–Lu–Yau curvature bound at scale 2 is at most 1: κ_LLY^(2)(G) ≤ 2/2 = 1.
- crossing_pairs_card_eq_crossing_edges_cardFor a finite simple graph G and a vertex set A, the number of ordered adjacent pairs (a, b) with a ∈ A and b ∈ Aᶜ equals the number of…
- cross_cut_card_ge_minDegree_of_diam_twoPlesník's cut lemma: in a finite connected graph G with diam(G) = 2, every nontrivial vertex cut (A, Aᶜ) has at least δ(G) crossing edges.
- graph_edge_connectivity_eq_minDegree_of_diam_twoPlesník's theorem: every finite connected graph of diameter 2 has edge-connectivity equal to its minimum degree, κ'(G) = δ(G).
The proof, explained
The proof reduces the goal to the minimum degree δ(G) using the fact that in any connected graph of diameter 2, the edge-connectivity κ'(G) equals δ(G). Because the Lin–Lu–Yau curvature lower bound at distance 2 is at most 1, multiplying this bound by the non-negative minimum degree δ(G) shows that δ(G) · κ_LLY^(2)(G) ≤ δ(G) = κ'(G).
The Lin–Lu–Yau curvature lower bound at distance 2 is at most 1: κ_LLY^(2)(G) ≤ 1.
This is an established property of connected graphs (`graph_lly_curvature_lower_bound_two_le_one`).
uses
graph_lly_curvature_lower_bound_two_le_onehave h1 : graph_lly_curvature_lower_bound G 2 ≤ 1 := graph_lly_curvature_lower_bound_two_le_one G hGThe edge-connectivity κ'(G) equals the minimum degree δ(G), reducing the goal to showing δ(G) · κ_LLY^(2)(G) ≤ δ(G).
For any connected graph of diameter 2, the edge-connectivity is known to equal the minimum degree (`graph_edge_connectivity_eq_minDegree_of_diam_two`). Rewriting κ'(G) to δ(G) in the goal reduces the required inequality to δ(G) · κ_LLY^(2)(G) ≤ δ(G).
uses
graph_edge_connectivity_eq_minDegree_of_diam_twohave h2 : graph_edge_connectivity G = G.minDegree := graph_edge_connectivity_eq_minDegree_of_diam_two G hG hd rw [h2]
δ(G) · κ_LLY^(2)(G) ≤ δ(G) · 1
Because the minimum degree δ(G) is a natural number, its real cast is non-negative (`Nat.cast_nonneg`). Multiplying both sides of the inequality κ_LLY^(2)(G) ≤ 1 by δ(G) on the left preserves the inequality (`mul_le_mul_of_nonneg_left`).
uses
mul_le_mul_of_nonneg_left,Nat.cast_nonneghave h3 : (G.minDegree : ℝ) * graph_lly_curvature_lower_bound G 2 ≤ (G.minDegree : ℝ) * 1 := by apply mul_le_mul_of_nonneg_left h1 exact Nat.cast_nonneg _
δ(G) · κ_LLY^(2)(G) ≤ δ(G)
Since δ(G) · 1 = δ(G), linear arithmetic (`linarith`) completes the proof from δ(G) · κ_LLY^(2)(G) ≤ δ(G) · 1.
linarith
graph_lly_curvature_lower_bound_two_le_one- In a connected graph, the Lin–Lu–Yau curvature lower bound at distance 2 is at most 1.
graph_edge_connectivity_eq_minDegree_of_diam_two- In a connected graph of diameter 2, the edge-connectivity equals the minimum degree.
mul_le_mul_of_nonneg_left- Multiplying an inequality b ≤ c on the left by a non-negative element a ≥ 0 yields a * b ≤ a * c.
Nat.cast_nonneg- The canonical embedding of any natural number into an ordered semiring is non-negative.
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 edge_connectivity_ge_min_degree_mul_lly_lower_bound_two {V : Type} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (hG : G.Connected) (hd : G.diam = 2) : (G.minDegree : ℝ) * graph_lly_curvature_lower_bound G 2 ≤ (graph_edge_connectivity G : ℝ) := by have h1 : graph_lly_curvature_lower_bound G 2 ≤ 1 := graph_lly_curvature_lower_bound_two_le_one G hG have h2 : graph_edge_connectivity G = G.minDegree := graph_edge_connectivity_eq_minDegree_of_diam_two G hG hd rw [h2] have h3 : (G.minDegree : ℝ) * graph_lly_curvature_lower_bound G 2 ≤ (G.minDegree : ℝ) * 1 := by apply mul_le_mul_of_nonneg_left h1 exact Nat.cast_nonneg _ linarith