not_forall_lly_positive_edge_connectivity_threshold_eq_ceil
It 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 triangle) has positive Lin–Lu–Yau curvature on every edge, while ⌈2·3/3 − 1⌉ = 1. The failure is not only this degenerate case: by exact computation c(5) = 2 while ⌈2·5/3 − 1⌉ = 3 (see lly_positive_edge_connectivity_threshold_five).
Statement
theorem not_forall_lly_positive_edge_connectivity_threshold_eq_ceil :
¬ ∀ n : ℕ, 3 ≤ n →
lly_positive_edge_connectivity_threshold n = ⌈(2 * (n : ℝ)) / 3 - 1⌉₊- Related work
- Answers OP-165 (a question proposed here from arXiv:2610.10559 (Edge-Connectivity versus Lin--Lu--Yau Curvature), Theorem 1.4, whose sharpness construction needs 2n/3 even and ≥ 6; the paper does not ask it) in the negative. Exact computation of c(n) for n ≤ 6 (curvatures via the paper's Theorem 2.2 and min-cost flow): c(3) = 0, c(4) = 2, c(5) = 2, c(6) = 3, against ⌈2n/3 − 1⌉ = 1, 2, 3, 3.
- Verified
- 22 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- 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…
- lly_positive_edge_connectivity_threshold_threec(3) = 0: every connected graph on 3 vertices has positive Lin–Lu–Yau curvature on every edge, whatever its edge-connectivity.
The proof, explained
The theorem is proved by contradiction using $n = 3$ as an explicit counterexample. Assuming the conjectured formula $c(n) = \lceil 2n/3 - 1 \rceil$ holds for all $n \ge 3$ forces $c(3) = \lceil 2 \cdot 3 / 3 - 1 \rceil = 1$. But the true threshold on 3 vertices is known to be $c(3) = 0$, producing the contradiction $0 = 1$.
Assuming the threshold formula holds for all $n \ge 3$, it must hold in particular for $n = 3$: $c(3) = \lceil 2 \cdot 3 / 3 - 1 \rceil$.
We argue by contradiction and assume that $c(n) = \lceil 2n/3 - 1 \rceil$ for all $n \ge 3$. Specializing this universal hypothesis to $n = 3$, using the reflexivity of inequality (`le_rfl`) to satisfy $3 \le 3$, yields $c(3) = \lceil 2 \cdot 3 / 3 - 1 \rceil$.
uses
le_rflintro h have h3 := h 3 le_rfl
A contradiction is reached because $c(3) = 0$ while the formula evaluates to $1$.
Rewriting with `lly_positive_edge_connectivity_threshold_three` substitutes the known value $c(3) = 0$, giving $0 = \lceil 2 \cdot 3 / 3 - 1 \rceil$. Numerical computation (`norm_num`) evaluates the right-hand side to $\lceil 1 \rceil = 1$, reducing the equality to $0 = 1$, which completes the contradiction.
uses
lly_positive_edge_connectivity_threshold_threerw [lly_positive_edge_connectivity_threshold_three] at h3 norm_num at h3
le_rfl- Every element of a preorder is less than or equal to itself ($a \le a$).
lly_positive_edge_connectivity_threshold_three- The Lin–Lu–Yau positive edge connectivity threshold for graphs on 3 vertices is 0 ($c(3) = 0$).
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 not_forall_lly_positive_edge_connectivity_threshold_eq_ceil : ¬ ∀ n : ℕ, 3 ≤ n → lly_positive_edge_connectivity_threshold n = ⌈(2 * (n : ℝ)) / 3 - 1⌉₊ := by intro h have h3 := h 3 le_rfl rw [lly_positive_edge_connectivity_threshold_three] at h3 norm_num at h3