AFTD Auto-Formalizing Theoretical Domains

lly_positive_edge_connectivity_threshold_five

theoremverifiedoriginal

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

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.

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

    lines 3–6

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

    lines 7–13

    uses Fintype.card_fin, graph_edge_connectivity_le_minDegree, lly_five_vertex_pos_of_min_degree_two

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

    lines 14–16

    uses Nat.sInf_mem, Nat.sInf_le

      have hne : S.Nonempty := ⟨2, h2S⟩
      have hmem : sInf S ∈ S := Nat.sInf_mem hne
      have hle2 : sInf S ≤ 2 := Nat.sInf_le h2S
  4. ¬ (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.

    lines 17–24

    uses five_vertex_t_star_connected_edge_connectivity.1, five_vertex_t_star_connected_edge_connectivity.2, lly_five_vertex_t_star_curvature

      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
  5. sInf S = 2

    Linear arithmetic over the natural numbers combines sInf S ≤ 2 and ¬(sInf S ≤ 1) to conclude that sInf S = 2.

    line 25

      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

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