lly_positive_edge_connectivity_threshold_five
c(5) = 2: every connected graph on 5 vertices with edge-connectivity at least 2 has positive Lin–Lu–Yau curvature on every edge, while the path-like tree with a vertex of degree 3 (edges 01, 03, 04, 12) has κ' = 1 and κ_LLY(0,1) = −1/3. So c(5) < ⌈2·5/3 − 1⌉ = 3: the threshold of OP-165 fails at n = 5 for a non-degenerate reason.
Statement
theorem lly_positive_edge_connectivity_threshold_five :
lly_positive_edge_connectivity_threshold 5 = 2- Related work
- Partial result on OP-165 (arXiv:2610.10559, after Theorem 1.4); found by exact computation over all graphs on 5 vertices (curvatures via the paper's Theorem 2.2 and min-cost flow).
- Verified
- 18 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 14
- lly_positive_edge_connectivity_thresholdc(n): the smallest natural number k such that every connected simple graph on n vertices with edge-connectivity at least k has positive…
- five_vertex_t_starThe tree on 5 vertices with edges 0–1, 0–3, 0–4, 1–2: the path 3–0–1–2 with an extra leaf 4 attached at 0.
- five_vertex_t_star_adj_decidableAdjacency in the T-graph is decidable.
- five_vertex_t_star_dist_eqIn the T-graph: d(0,1) = 1, d(0,2) = 2, d(3,1) = 2, d(4,1) = 2, d(3,2) = d(4,2) = 3.
- five_vertex_t_star_wasserstein_leFor the T-graph and α in [2/5, 1], the explicit plan π(0,0)=(1−α)/2, π(0,1)=(5α−2)/3, π(0,2)=(1−α)/6, π(1,2)=(1−α)/3, π(3,1)=(1−α)/3,…
- five_vertex_t_star_wasserstein_geFor the T-graph and α in [0,1], 4/3 − α/3 ≤ W(μ_0^α, μ_1^α), because f(v) = d(v,2) is 1-Lipschitz and Σ f μ_0^α − Σ f μ_1^α = (2α +…
- five_vertex_t_star_connected_edge_connectivityThe T-graph (edges 0–1, 0–3, 0–4, 1–2) is connected and has edge-connectivity κ' = 1 (it is a tree).
- lly_five_vertex_t_star_curvatureFor the tree on 5 vertices with edges 0–1, 0–3, 0–4, 1–2 one has κ_LLY(0,1) = −1/3.
- five_vertex_min_degree_two_ediam_le_twoEvery graph on 5 vertices with minimum degree at least 2 has diameter at most 2, hence is connected.
- 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.
- lly_five_vertex_pos_of_min_degree_twoEvery connected graph on 5 vertices with minimum degree at least 2 has positive Lin–Lu–Yau curvature on every edge.
- 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_edge_connectivity_le_minDegreeEdge-connectivity is at most the minimum degree, κ'(G) ≤ δ(G) (for at least two vertices).
The proof, explained
The threshold c(5) is the minimal edge-connectivity k guaranteeing that every connected 5-vertex graph has strictly positive Lin–Lu–Yau curvature on every edge. The upper bound c(5) ≤ 2 holds because edge-connectivity at least 2 forces minimum degree at least 2, which suffices for positive curvature on all edges of any connected 5-vertex graph. The lower bound c(5) > 1 is witnessed by the tree on 5 vertices with a degree-3 vertex and a single edge-connectivity cut, where the central edge has negative curvature -1/3. Together, these bounds establish c(5) = 2.
Define S as the set of edge-connectivity thresholds that ensure positive Lin–Lu–Yau curvature on all edges for connected 5-vertex graphs.
Unfolding the definition of lly_positive_edge_connectivity_threshold 5 sets up the problem as finding the infimum of the set S ⊆ ℕ of bounds k such that any connected 5-vertex graph with edge-connectivity at least k has strictly positive Lin–Lu–Yau curvature on all edges. The goal is to prove sInf S = 2.
unfold lly_positive_edge_connectivity_threshold set S : Set ℕ := {k : ℕ | ∀ (G : SimpleGraph (Fin 5)) [DecidableRel G.Adj], G.Connected → k ≤ graph_edge_connectivity G → ∀ (x y : Fin 5), G.Adj x y → 0 < graph_lly_curvature G x y}
2 ∈ S
Let G be a connected graph on Fin 5 with edge-connectivity at least 2. By graph_edge_connectivity_le_minDegree, the minimum degree δ(G) is at least the edge-connectivity, so δ(G) ≥ 2. By lly_five_vertex_pos_of_min_degree_two, every connected 5-vertex graph with minimum degree at least 2 has strictly positive Lin–Lu–Yau curvature on all edges, so 2 satisfies the condition defining S.
uses
Fintype.card_fin,graph_edge_connectivity_le_minDegree,lly_five_vertex_pos_of_min_degree_twohave h2S : 2 ∈ S := by intro G inst hconn hk x y hxy have hcard : Fintype.card (Fin 5) = 5 := Fintype.card_fin 5 have hmin : 2 ≤ G.minDegree := by have hle := graph_edge_connectivity_le_minDegree G omega exact lly_five_vertex_pos_of_min_degree_two G hcard hconn hmin x y hxy
sInf S ∈ S and sInf S ≤ 2
Since 2 ∈ S, the set S is nonempty. In ℕ, every nonempty set contains its infimum (Nat.sInf_mem), and the infimum is bounded above by any element of the set, here 2 (Nat.sInf_le).
uses
Nat.sInf_mem,Nat.sInf_lehave hne : S.Nonempty := ⟨2, h2S⟩ have hmem : sInf S ∈ S := Nat.sInf_mem hne have hle2 : sInf S ≤ 2 := Nat.sInf_le h2S
¬ (sInf S ≤ 1)
Assume for contradiction that sInf S ≤ 1. The counterexample tree five_vertex_t_star is connected and has edge-connectivity 1 by five_vertex_t_star_connected_edge_connectivity.1 and five_vertex_t_star_connected_edge_connectivity.2. Since sInf S ≤ 1, the definition of S implies that every edge of this tree must have positive curvature, so the edge (0, 1) satisfies κ_LLY(0, 1) > 0. However, lly_five_vertex_t_star_curvature computes that κ_LLY(0, 1) = -1/3. This contradiction (0 < -1/3) refutes sInf S ≤ 1.
uses
five_vertex_t_star_connected_edge_connectivity.1,five_vertex_t_star_connected_edge_connectivity.2,lly_five_vertex_t_star_curvaturehave hnot_le1 : ¬ (sInf S ≤ 1) := by intro hle1 have hT_conn := five_vertex_t_star_connected_edge_connectivity.1 have hT_ec := five_vertex_t_star_connected_edge_connectivity.2 have hT_adj : five_vertex_t_star.Adj 0 1 := by decide have hcurv := hmem five_vertex_t_star hT_conn (by omega) 0 1 hT_adj have hval := lly_five_vertex_t_star_curvature linarith
sInf S = 2
Linear arithmetic over the natural numbers combines sInf S ≤ 2 and ¬(sInf S ≤ 1) to conclude that sInf S = 2.
omega
Fintype.card_fin- For any n : ℕ, the cardinality of Fin n is n.
graph_edge_connectivity_le_minDegree- The edge-connectivity of any finite nontrivial graph is at most its minimum vertex degree.
lly_five_vertex_pos_of_min_degree_two- Every connected graph on 5 vertices with minimum degree at least 2 has strictly positive Lin–Lu–Yau curvature on every edge.
Nat.sInf_mem- A nonempty set of natural numbers contains its infimum (minimum).
Nat.sInf_le- The infimum of a set of natural numbers is less than or equal to every element of the set.
five_vertex_t_star_connected_edge_connectivity.1- The five-vertex tree five_vertex_t_star is connected.
five_vertex_t_star_connected_edge_connectivity.2- The five-vertex tree five_vertex_t_star has edge-connectivity equal to 1.
lly_five_vertex_t_star_curvature- The Lin–Lu–Yau curvature of the edge (0, 1) in five_vertex_t_star is -1/3.
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_positive_edge_connectivity_threshold_five : lly_positive_edge_connectivity_threshold 5 = 2 := by unfold lly_positive_edge_connectivity_threshold set S : Set ℕ := {k : ℕ | ∀ (G : SimpleGraph (Fin 5)) [DecidableRel G.Adj], G.Connected → k ≤ graph_edge_connectivity G → ∀ (x y : Fin 5), G.Adj x y → 0 < graph_lly_curvature G x y} have h2S : 2 ∈ S := by intro G inst hconn hk x y hxy have hcard : Fintype.card (Fin 5) = 5 := Fintype.card_fin 5 have hmin : 2 ≤ G.minDegree := by have hle := graph_edge_connectivity_le_minDegree G omega exact lly_five_vertex_pos_of_min_degree_two G hcard hconn hmin x y hxy have hne : S.Nonempty := ⟨2, h2S⟩ have hmem : sInf S ∈ S := Nat.sInf_mem hne have hle2 : sInf S ≤ 2 := Nat.sInf_le h2S have hnot_le1 : ¬ (sInf S ≤ 1) := by intro hle1 have hT_conn := five_vertex_t_star_connected_edge_connectivity.1 have hT_ec := five_vertex_t_star_connected_edge_connectivity.2 have hT_adj : five_vertex_t_star.Adj 0 1 := by decide have hcurv := hmem five_vertex_t_star hT_conn (by omega) 0 1 hT_adj have hval := lly_five_vertex_t_star_curvature linarith omega