AFTD Auto-Formalizing Theoretical Domains

lly_five_vertex_pos_of_min_degree_two

theoremverified

Every connected graph on 5 vertices with minimum degree at least 2 has positive Lin–Lu–Yau curvature on every edge.

Statement

theorem lly_five_vertex_pos_of_min_degree_two {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) [DecidableRel G.Adj] (hcard : Fintype.card V = 5) (hG : G.Connected)
    (hδ : 2 ≤ G.minDegree) (x y : V) (hxy : G.Adj x y) : 0 < graph_lly_curvature G x y
Source
step towards lly_positive_edge_connectivity_threshold_five
Verified
18 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
  • five_vertex_min_degree_two_wasserstein_lt_oneEvery connected graph on 5 vertices with minimum degree at least 2 has, for each edge xy, some α ∈ (0, 1) with W(μ_x^α, μ_y^α) < 1.
  • 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,…
  • 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…
  • graph_lly_curvatureThe Lin–Lu–Yau curvature κ_LLY(x, y) = lim_{α → 1⁻} κ_α(x, y)/(1 − α).
Used by 1

The proof, explained

The proof establishes positive Lin–Lu–Yau curvature by reducing it to a Wasserstein distance condition. For any connected graph on 5 vertices with minimum degree at least 2, a diameter-based transport plan argument produces an idleness parameter α ∈ (0, 1) whose lazy random walk measures have Wasserstein distance strictly less than 1. Positivity of the curvature then follows immediately from the general criterion relating Wasserstein distance to Lin–Lu–Yau curvature.

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

    By `five_vertex_min_degree_two_wasserstein_lt_one`, the hypotheses that G is connected, has 5 vertices, and has minimum degree at least 2 guarantee the existence of a parameter α ∈ (0, 1) for which the Wasserstein distance between the lazy random walk (idle) measures at adjacent vertices x and y is strictly less than 1.

    line 5

    uses five_vertex_min_degree_two_wasserstein_lt_one

      obtain ⟨α, hα0, hα1, hW⟩ := five_vertex_min_degree_two_wasserstein_lt_one G hcard hG hδ x y hxy
  2. The Lin–Lu–Yau curvature on the edge xy is strictly positive.

    Applying the general criterion `graph_lly_curvature_pos_of_wasserstein_lt_one`, the existence of an α ∈ (0, 1) with Wasserstein distance strictly less than 1 implies that the Lin–Lu–Yau curvature on the edge xy is strictly positive.

    line 6

    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
five_vertex_min_degree_two_wasserstein_lt_one
in any connected graph on 5 vertices with minimum degree at least 2, for any two adjacent vertices x and y, 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
graph_lly_curvature_pos_of_wasserstein_lt_one
for any connected graph and adjacent vertices x and y, if the Wasserstein distance between the idle measures at x and y is strictly less than 1 for some α ∈ (0, 1), then the Lin–Lu–Yau curvature on the edge xy 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

/-- Every connected graph on 5 vertices with minimum degree at least 2 has positive Lin–Lu–Yau curvature on every edge: apply the Wasserstein < 1 criterion at the α produced by the diameter-2 plan argument. This is the `2 ∈ S` half of the parent. -/theorem lly_five_vertex_pos_of_min_degree_two {V : Type*} [Fintype V] [DecidableEq V]    (G : SimpleGraph V) [DecidableRel G.Adj] (hcard : Fintype.card V = 5) (hG : G.Connected)    (hδ : 2 ≤ G.minDegree) (x y : V) (hxy : G.Adj x y) : 0 < graph_lly_curvature G x y := by  obtain ⟨α, hα0, hα1, hW⟩ := five_vertex_min_degree_two_wasserstein_lt_one G hcard hG 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