lly_positive_edge_connectivity_threshold_three
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
- not_forall_lly_positive_edge_connectivity_threshold_eq_ceilIt is not true that c(n) = ⌈2n/3 − 1⌉ for all n ≥ 3. Already c(3) = 0, since every connected graph on 3 vertices (the path and the…
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.
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.
uses
Nat.eq_zero_of_le_zero,Nat.sInf_leunfold lly_positive_edge_connectivity_threshold apply Nat.eq_zero_of_le_zero apply Nat.sInf_le
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`).
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
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.
uses
graph_lly_curvature_pos_of_threefin_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.
- The proof uses finite case exhaustion via `fin_cases` and `all_goals first` to check all nine vertex pairs $(x, y)$ and find the remaining vertex $z \in \{0, 1, 2\} \setminus \{x, y\}$, discharging numerical distinctness checks automatically with `decide`. On paper, one simply selects the unique remaining vertex without enumerating cases.
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_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))