not_cut_layer_potential_avg_bound
The statement cut_layer_potential_avg_bound is false: The statement has no hypothesis guaranteeing G.minDegree > 0. When G has an isolated vertex, minDegree = 0, so the right-hand side is 2·(cut count)/0 = 0 in ℝ. A concrete counterexample: V = Fin 2, G = ⊥ (empty graph), X = {1}, x = 0, y = 1. Then x ∈ Xᶜ, y ∈ X, both have no neighbours at all so the "interior" hypotheses hold. We have degree(x) = degree(y) = 0, neighborFinset of each is empty, and minDegree = 0. The left-hand side is 3 − (∑_{\text{empty}} f)/0 + (∑_{\text{empty}} f)/0 = 3 − 0 + 0 = 3, while the right-hand side is 2·|E(X,Xᶜ)|/0 = 2·0/0 = 0. So the claim would assert 3 ≤ 0, which is false. The intended lemma is only true under the additional hypothesis 0 < G.minDegree (equivalently, every vertex has degree at least 1), which is what allows dividing by δ(G). Verified in Lean: the negation of the statement is proved for this instance.
Statement
theorem not_cut_layer_potential_avg_bound : ¬ (∀ {V : Type} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (X : Finset V) (x y : V) (hx : x ∈ (Xᶜ : Finset V)) (hx_no : ∀ u ∈ X, ¬ G.Adj x u) (hy : y ∈ X) (hy_no : ∀ w ∈ (Xᶜ : Finset V), ¬ G.Adj y w), let f := cut_layer_potential G X (3 - (∑ a ∈ G.neighborFinset x, f a) / (G.degree x : ℝ) + (∑ b ∈ G.neighborFinset y, f b) / (G.degree y : ℝ)) ≤ 2 * ((G.edgeFinset.filter (fun e => ∃ u ∈ X, ∃ v ∈ (Xᶜ : Finset V), e = s(u, v))).card : ℝ) / (G.minDegree : ℝ))
- Related work
- refutes `cut_layer_potential_avg_bound`
- Verified
- 18 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- cut_layer_potentialThe 4-layer potential takes value 0 on vertices of X with no neighbors in Xᶜ, 1 on vertices of X with a neighbor in Xᶜ, 2 on vertices of…
The proof, explained
The proof proceeds by contradiction, refuting the universally quantified inequality by providing an explicit counterexample. By choosing the empty graph on the two-element set {0, 1} with X = {1}, x = 0, and y = 1, all interior and disjointness hypotheses are vacuously satisfied since the graph has no edges. Because the vertex degrees, cut size, and minimum degree are all 0, real division by zero evaluates to 0, reducing the inequality to 3 ≤ 0 and producing a contradiction.
Assume for contradiction that the inequality holds universally for all finite graphs, subsets, and vertices satisfying the hypotheses.
The proof introduces the universally quantified proposition as hypothesis h, reducing the goal to deriving False.
intro hInstantiating the inequality on the empty graph on two vertices produces a concrete inequality hinst.
We specialize the universal hypothesis h to V = Fin 2 = {0, 1}, the empty graph G = ⊥, the subset X = {1}, x = 0, and y = 1. The side conditions are verified immediately: 0 ∈ {1}ᶜ and 1 ∈ {1} hold by finite computation (decide), while x has no neighbors in X and y has no neighbors in Xᶜ hold vacuously because the empty graph has no edges.
have hinst := h (V := Fin 2) (G := (⊥ : SimpleGraph (Fin 2))) (X := ({1} : Finset (Fin 2))) (x := 0) (y := 1) (by decide) (by intro u _; simp) (by decide) (by intro w _; simp)
The left-hand side of hinst simplifies to 3.
Because G = ⊥ has no edges, the neighborhoods of 0 and 1 are empty (SimpleGraph.neighborSet_bot, Set.toFinset_empty), their degrees are 0, and the sums over their neighbors are 0 (Finset.sum_empty). In ℝ, 0 / 0 = 0 (zero_div), so the two quotient terms vanish, simplifying the left-hand side 3 - 0/0 + 0/0 to 3.
uses
SimpleGraph.neighborFinset,SimpleGraph.degree,SimpleGraph.edgeFinset,SimpleGraph.neighborSet_bot,Set.toFinset_empty,Finset.card_empty,Finset.sum_empty,Nat.cast_zero,zero_div,sub_zero,add_zero,SimpleGraph.bot_adj,not_false_eq_true,exists_const,Finset.mem_singletonsimp only [SimpleGraph.neighborFinset, SimpleGraph.degree, SimpleGraph.edgeFinset, SimpleGraph.neighborSet_bot, Set.toFinset_empty, Finset.card_empty, Finset.sum_empty, Nat.cast_zero, zero_div, sub_zero, add_zero, SimpleGraph.bot_adj, not_false_eq_true, exists_const, Finset.mem_singleton] at hinst
A contradiction is derived because hinst asserts 3 ≤ 0.
The empty graph has no edges, so the number of cut edges between X and Xᶜ is 0. With minDegree = 0, the right-hand side evaluates to 2 · 0 / 0 = 0. The hypothesis hinst thus reduces to 3 ≤ 0, and numerical evaluation (norm_num) refutes this inequality, deriving False.
norm_num at hinst
SimpleGraph.neighborFinset- The finset of neighbors of a vertex v in a graph.
SimpleGraph.degree- The degree of a vertex v, defined as the cardinality of its neighbor finset.
SimpleGraph.edgeFinset- The finset of all edges in a graph with a finite edge set.
SimpleGraph.neighborSet_bot- In the empty graph ⊥, the neighbor set of any vertex is empty.
Set.toFinset_empty- The finset corresponding to the empty set ∅ is the empty finset ∅.
Finset.card_empty- The cardinality of the empty finset is 0.
Finset.sum_empty- The sum of any function over the empty finset is 0.
Nat.cast_zero- The natural number 0 cast to an additive monoid with one (such as ℝ) equals 0.
zero_div- Zero divided by any element in a division structure with zero equals zero (0 / a = 0).
sub_zero- Subtracting zero leaves any element unchanged (a - 0 = a).
add_zero- Adding zero leaves any element unchanged (a + 0 = a).
SimpleGraph.bot_adj- In the empty graph ⊥, adjacency between any two vertices is false.
not_false_eq_true- The negation of False is True.
exists_const- Over a nonempty type, the existential quantification of a constant proposition (∃ x, b) is equivalent to b.
Finset.mem_singleton- An element b is in the singleton finset {a} if and only if b = a.
- In Lean's formalization of the real numbers ℝ, division by zero is defined to yield zero (i.e. x / 0 = 0 for any x). Consequently, dividing by the degrees and the minimum degree, which are all 0 in the empty graph, produces 0 rather than an undefined value.
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_cut_layer_potential_avg_bound : ¬ (∀ {V : Type} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (X : Finset V) (x y : V) (hx : x ∈ (Xᶜ : Finset V)) (hx_no : ∀ u ∈ X, ¬ G.Adj x u) (hy : y ∈ X) (hy_no : ∀ w ∈ (Xᶜ : Finset V), ¬ G.Adj y w), let f := cut_layer_potential G X (3 - (∑ a ∈ G.neighborFinset x, f a) / (G.degree x : ℝ) + (∑ b ∈ G.neighborFinset y, f b) / (G.degree y : ℝ)) ≤ 2 * ((G.edgeFinset.filter (fun e => ∃ u ∈ X, ∃ v ∈ (Xᶜ : Finset V), e = s(u, v))).card : ℝ) / (G.minDegree : ℝ)) := by intro h have hinst := h (V := Fin 2) (G := (⊥ : SimpleGraph (Fin 2))) (X := ({1} : Finset (Fin 2))) (x := 0) (y := 1) (by decide) (by intro u _; simp) (by decide) (by intro w _; simp) simp only [SimpleGraph.neighborFinset, SimpleGraph.degree, SimpleGraph.edgeFinset, SimpleGraph.neighborSet_bot, Set.toFinset_empty, Finset.card_empty, Finset.sum_empty, Nat.cast_zero, zero_div, sub_zero, add_zero, SimpleGraph.bot_adj, not_false_eq_true, exists_const, Finset.mem_singleton] at hinst norm_num at hinst