AFTD Auto-Formalizing Theoretical Domains

edge_connectivity_ge_min_degree_mul_lly_lower_bound_two

theoremverifiedformalization

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

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

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

    lines 5–6

    uses graph_lly_curvature_lower_bound_two_le_one

      have h1 : graph_lly_curvature_lower_bound G 2 ≤ 1 :=
        graph_lly_curvature_lower_bound_two_le_one G hG
  2. The 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).

    lines 7–9

    uses graph_edge_connectivity_eq_minDegree_of_diam_two

      have h2 : graph_edge_connectivity G = G.minDegree :=
        graph_edge_connectivity_eq_minDegree_of_diam_two G hG hd
      rw [h2]
  3. δ(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`).

    lines 10–12

    uses mul_le_mul_of_nonneg_left, Nat.cast_nonneg

      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 _
  4. δ(G) · κ_LLY^(2)(G) ≤ δ(G)

    Since δ(G) · 1 = δ(G), linear arithmetic (`linarith`) completes the proof from δ(G) · κ_LLY^(2)(G) ≤ δ(G) · 1.

    line 13

      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

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