AFTD Auto-Formalizing Theoretical Domains

not_forall_lly_positive_edge_connectivity_threshold_eq_ceil

theoremverifiedoriginal

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

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

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

    lines 4–5

    uses le_rfl

      intro h
      have h3 := h 3 le_rfl
  2. 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.

    lines 6–7

    uses lly_positive_edge_connectivity_threshold_three

      rw [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

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