AFTD Auto-Formalizing Theoretical Domains

lly_positive_edge_connectivity_threshold_three

theoremverifiedoriginal

c(3) = 0: every connected graph on 3 vertices has positive Lin–Lu–Yau curvature on every edge, whatever its edge-connectivity.

Statement

theorem lly_positive_edge_connectivity_threshold_three :
    lly_positive_edge_connectivity_threshold 3 = 0
Related work
Partial result on OP-165 (arXiv:2610.10559, after Theorem 1.4): the threshold ⌈2n/3 − 1⌉ = 1 is not attained at n = 3.
Verified
10 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • 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…
  • graph_lly_curvature_pos_of_threeIn a finite connected graph with exactly three vertices x, y, z, every edge xy has positive Lin–Lu–Yau curvature.
  • 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…
Used by 1

The proof, explained

To show that the threshold $c(3)$ is 0, it suffices by definition of the infimum to show that $k = 0$ satisfies the condition: every connected graph on 3 vertices has strictly positive Lin–Lu–Yau curvature on every edge. For any such graph $G$ and edge $x \sim y$, the endpoints $x$ and $y$ are distinct. An exhaustive case split on all pairs of vertices $(x, y) \in \{0, 1, 2\}^2$ rules out the diagonal cases $x = y$ and identifies the unique third vertex $z \in \{0, 1, 2\} \setminus \{x, y\}$ in the off-diagonal cases. The claim then follows from the helper theorem `graph_lly_curvature_pos_of_three`, which establishes positive curvature on any edge of a 3-vertex connected graph.

  1. It suffices to show that $k = 0$ satisfies the defining condition of the threshold, meaning every connected graph on 3 vertices has strictly positive Lin–Lu–Yau curvature on every edge.

    Unfolding the definition, the threshold is the infimum of all natural numbers $k$ for which $k$-edge-connectivity implies positive Lin–Lu–Yau curvature on all edges. By `Nat.eq_zero_of_le_zero`, any natural number bounded above by 0 equals 0, and by `Nat.sInf_le`, an infimum is bounded above by any member of the set. Thus it suffices to show that $0$ belongs to the set.

    lines 3–5

    uses Nat.eq_zero_of_le_zero, Nat.sInf_le

      unfold lly_positive_edge_connectivity_threshold
      apply Nat.eq_zero_of_le_zero
      apply Nat.sInf_le
  2. Given an arbitrary connected graph $G$ on 3 vertices and an edge $x \sim y$, the endpoints are distinct ($x \ne y$), and any three pairwise distinct vertices exhaust the vertex set $\mathrm{Fin}\ 3$.

    We introduce the graph $G$, the connectivity hypothesis `hG`, the trivial condition $0 \le \mathrm{graph\_edge\_connectivity}(G)$, and the edge `hxy` between $x$ and $y$. We establish two local facts: first, by finite exhaustion (`decide`), any three pairwise distinct vertices $a, b, c \in \mathrm{Fin}\ 3$ cover every vertex (`hall`); second, adjacency in a simple graph requires $x \ne y$ (`hne`).

    lines 6–8

      intro G _ hG _ x y hxy
      have hall : ∀ a b c : Fin 3, a ≠ b → c ≠ a → c ≠ b → ∀ w, w = a ∨ w = b ∨ w = c := by decide
      have hne : x ≠ y := G.ne_of_adj hxy
  3. Every edge $x \sim y$ in $G$ has strictly positive Lin–Lu–Yau curvature.

    We perform exhaustive case analysis on the coordinates of $x, y \in \mathrm{Fin}\ 3$, yielding nine cases. The three diagonal cases $x = y$ immediately contradict $x \ne y$ (`absurd rfl hne`). In each of the six off-diagonal cases, the search pattern finds the unique remaining vertex $z \in \{0, 1, 2\}$ distinct from both $x$ and $y$. Applying `graph_lly_curvature_pos_of_three` with witness $z$ and the coverage property `hall` proves that the curvature on the edge is strictly positive.

    lines 9–17

    uses graph_lly_curvature_pos_of_three

      fin_cases x <;> fin_cases y
      all_goals first
        | exact absurd rfl hne
        | exact graph_lly_curvature_pos_of_three G hG _ _ 0 hxy (by decide) (by decide)
            (hall _ _ _ (by decide) (by decide) (by decide))
        | exact graph_lly_curvature_pos_of_three G hG _ _ 1 hxy (by decide) (by decide)
            (hall _ _ _ (by decide) (by decide) (by decide))
        | exact graph_lly_curvature_pos_of_three G hG _ _ 2 hxy (by decide) (by decide)
            (hall _ _ _ (by decide) (by decide) (by decide))
Nat.eq_zero_of_le_zero
A natural number bounded above by zero is zero ($n \le 0 \implies n = 0$).
Nat.sInf_le
The infimum of a set of natural numbers is bounded above by any element of the set ($m \in s \implies \inf s \le m$).
graph_lly_curvature_pos_of_three
In any connected graph on three vertices $x, y, z$, any edge between $x$ and $y$ has strictly positive Lin–Lu–Yau curvature.

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_three :    lly_positive_edge_connectivity_threshold 3 = 0 := by  unfold lly_positive_edge_connectivity_threshold  apply Nat.eq_zero_of_le_zero  apply Nat.sInf_le  intro G _ hG _ x y hxy  have hall : ∀ a b c : Fin 3, a ≠ b → c ≠ a → c ≠ b → ∀ w, w = a ∨ w = b ∨ w = c := by decide  have hne : x ≠ y := G.ne_of_adj hxy  fin_cases x <;> fin_cases y  all_goals first    | exact absurd rfl hne    | exact graph_lly_curvature_pos_of_three G hG _ _ 0 hxy (by decide) (by decide)        (hall _ _ _ (by decide) (by decide) (by decide))    | exact graph_lly_curvature_pos_of_three G hG _ _ 1 hxy (by decide) (by decide)        (hall _ _ _ (by decide) (by decide) (by decide))    | exact graph_lly_curvature_pos_of_three G hG _ _ 2 hxy (by decide) (by decide)        (hall _ _ _ (by decide) (by decide) (by decide))
See it in the graphDiscuss this resultChallenge it