AFTD Auto-Formalizing Theoretical Domains

not_cut_layer_potential_avg_bound

theoremverifiedoriginal

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.

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

    line 10

      intro h
  2. Instantiating 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.

    lines 11–12

      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)
  3. 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.

    lines 13–16

    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_singleton

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

    line 17

      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.

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