AFTD Auto-Formalizing Theoretical Domains

graph_lly_curvature_lower_bound_two_le_one

theoremverified

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

Statement

theorem graph_lly_curvature_lower_bound_two_le_one {V : Type} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) [DecidableRel G.Adj] (hG : G.Connected) :
    graph_lly_curvature_lower_bound G 2 ≤ 1
Source
step towards edge_connectivity_ge_min_degree_mul_lly_lower_bound_two
Verified
18 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
Used by 1

The proof, explained

The scale-2 Lin–Lu–Yau curvature lower bound of a graph G is the infimum of κ_LLY(x, y) over all pairs of vertices at distance 2. If no pair of vertices is at distance 2, the set is empty, so its infimum is 0 ≤ 1 by Lean's convention for the real numbers. Otherwise, there exists a pair x, y with d(x, y) = 2; since the vertex set is finite, the set of curvatures is finite and bounded below, so its infimum is at most κ_LLY(x, y). Because d(x, y) = 2 implies x ≠ y, the general upper bound κ_LLY(x, y) ≤ 2 / d(x, y) = 1 applies, and transitivity completes the proof.

  1. Unfold the definition of the scale-2 curvature bound and split into cases based on whether any pair of vertices has distance 2.

    By definition, graph_lly_curvature_lower_bound G 2 is the infimum of the set of curvatures κ_LLY(x, y) over all pairs of vertices at distance 2. We use Set.eq_empty_or_nonempty to separate the cases where this set of curvatures is empty or nonempty.

    lines 5–6

    uses Set.eq_empty_or_nonempty

      unfold graph_lly_curvature_lower_bound
      rcases Set.eq_empty_or_nonempty {κ | ∃ x y : V, G.dist x y = 2 ∧ graph_lly_curvature G x y = κ} with he | hne_set
  2. If no two vertices are at distance 2, the scale-2 curvature lower bound is at most 1.

    When the set of distance-2 curvatures is empty, its infimum in ℝ evaluates to 0 by Real.sInf_empty. Arithmetic simplification (norm_num) then confirms 0 ≤ 1.

    lines 7–8

    uses Real.sInf_empty

      · rw [he, Real.sInf_empty]
        norm_num
  3. In the nonempty case, the infimum is at most the curvature κ_LLY(x, y) of some pair of vertices at distance 2.

    Because the set is nonempty, there exist vertices x and y with G.dist x y = 2. Since V is a finite type, the Cartesian product V × V is finite, and the range of the curvature function on V × V is finite by Set.finite_range. The set of scale-2 curvatures is a subset of this range, hence finite and bounded below. By csInf_le, the infimum is bounded above by κ_LLY(x, y).

    lines 9–16

    uses Set.finite_range, csInf_le

      · rcases hne_set with ⟨_, x, y, hxy, rfl⟩
        have hfin : ({κ | ∃ x y : V, G.dist x y = 2 ∧ graph_lly_curvature G x y = κ} : Set ℝ).Finite := by
          have : {κ | ∃ x y : V, G.dist x y = 2 ∧ graph_lly_curvature G x y = κ} ⊆
              Set.range (fun p : V × V => graph_lly_curvature G p.1 p.2) := by
            rintro _ ⟨a, b, -, rfl⟩
            exact ⟨(a, b), rfl⟩
          exact (Set.finite_range _).subset this
        have hle := csInf_le hfin.bddBelow ⟨x, y, hxy, rfl⟩
  4. The curvature κ_LLY(x, y) between the chosen vertices is at most 1.

    Since G.dist x y = 2, x ≠ y (as G.dist x x = 0 ≠ 2). Applying graph_lly_curvature_le_two_div_dist to the distinct vertices x and y in the connected graph G gives κ_LLY(x, y) ≤ 2 / G.dist x y. Substituting G.dist x y = 2 and simplifying 2 / 2 yields κ_LLY(x, y) ≤ 1.

    lines 17–22

    uses graph_lly_curvature_le_two_div_dist

        have hne : x ≠ y := by
          rintro rfl
          simp at hxy
        have hcurv := graph_lly_curvature_le_two_div_dist G hG x y hne
        rw [hxy] at hcurv
        norm_num at hcurv
  5. The scale-2 curvature lower bound of G is at most 1.

    Combining the inequality sInf {κ | ...} ≤ κ_LLY(x, y) with κ_LLY(x, y) ≤ 1 via transitivity (le_trans) establishes that graph_lly_curvature_lower_bound G 2 ≤ 1.

    line 23

    uses le_trans

        exact le_trans hle hcurv
Set.eq_empty_or_nonempty
Every set is either empty or nonempty.
Real.sInf_empty
The infimum of the empty set of real numbers is 0.
Set.finite_range
The range of a function defined on a finite domain is finite.
csInf_le
In a conditionally complete lattice such as ℝ, the infimum of a set bounded below is less than or equal to any element of that set.
graph_lly_curvature_le_two_div_dist
In any finite connected graph, the Lin–Lu–Yau curvature between distinct vertices x and y is at most 2 / d(x, y).
le_trans
Inequality is transitive: if a ≤ b and b ≤ c, then a ≤ c.

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

/-- The scale-2 curvature bound is at most 1, since κ_LLY(x,y) ≤ 2/d(x,y) = 1 for d(x,y)=2. -/theorem graph_lly_curvature_lower_bound_two_le_one {V : Type} [Fintype V] [DecidableEq V]    (G : SimpleGraph V) [DecidableRel G.Adj] (hG : G.Connected) :    graph_lly_curvature_lower_bound G 2 ≤ 1 := by  unfold graph_lly_curvature_lower_bound  rcases Set.eq_empty_or_nonempty {κ | ∃ x y : V, G.dist x y = 2 ∧ graph_lly_curvature G x y = κ} with he | hne_set  · rw [he, Real.sInf_empty]    norm_num  · rcases hne_set with ⟨_, x, y, hxy, rfl⟩    have hfin : ({κ | ∃ x y : V, G.dist x y = 2 ∧ graph_lly_curvature G x y = κ} : Set ℝ).Finite := by      have : {κ | ∃ x y : V, G.dist x y = 2 ∧ graph_lly_curvature G x y = κ} ⊆          Set.range (fun p : V × V => graph_lly_curvature G p.1 p.2) := by        rintro _ ⟨a, b, -, rfl⟩        exact ⟨(a, b), rfl⟩      exact (Set.finite_range _).subset this    have hle := csInf_le hfin.bddBelow ⟨x, y, hxy, rfl⟩    have hne : x ≠ y := by      rintro rfl      simp at hxy    have hcurv := graph_lly_curvature_le_two_div_dist G hG x y hne    rw [hxy] at hcurv    norm_num at hcurv    exact le_trans hle hcurv
See it in the graphDiscuss this resultChallenge it