AFTD Auto-Formalizing Theoretical Domains

simple_graph_cut_weight_nonneg

theoremverified

In any simple graph G on a finite type V with decidable equality and decidable adjacency, with edge weighting w : G.edgeSet → ℝ satisfying w e ≥ 0 for all edges e, the cut weight simple_graph_cut_weight G w S is nonnegative for every vertex subset S : Finset V.

Statement

theorem simple_graph_cut_weight_nonneg {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) [DecidableRel G.Adj] (w : G.edgeSet → ℝ) (hw : ∀ e, 0 ≤ w e) (S : Finset V) :
    0 ≤ simple_graph_cut_weight G w S
Source
folklore
Verified
09 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • simple_graph_cut_weightGiven a finite type V with decidable equality, a simple graph G on V with decidable adjacency, an edge weighting w : G.edgeSet → ℝ, and a…

Read back from the Lean

For any finite type $V$ with decidable equality, any simple graph $G$ on $V$ with decidable adjacency, any real-valued edge weight function $w : G\text{.edgeSet} \to \mathbb{R}$ such that $w(e) \ge 0$ for all edges $e$, and any subset of vertices $S \subseteq V$ (as a Finset), the cut weight simple_graph_cut_weight G w S is non-negative ($0 \le \text{simple\_graph\_cut\_weight } G\ w\ S$).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The cut weight of a vertex subset S is defined as the sum over all edges of an indicator term: w(e) if the edge e crosses the cut between S and its complement, and 0 otherwise. Since a finite sum of nonnegative terms is nonnegative, it suffices to check that each summand is nonnegative. Each edge contributes either its weight w(e), which is nonnegative by hypothesis, or 0, so every term is nonnegative.

  1. To show that the cut weight is nonnegative, it suffices to show that each edge's contribution is nonnegative.

    Unfolding the definition of `simple_graph_cut_weight`, the cut weight is a finite sum over all edges e of an indicator expression: w(e) if e has one endpoint in S and the other outside S, and 0 otherwise. Applying `Finset.sum_nonneg` reduces the goal of showing that the sum is nonnegative to showing that every summand is nonnegative.

    lines 5–6

    uses Finset.sum_nonneg

      unfold simple_graph_cut_weight
      apply Finset.sum_nonneg
  2. Each edge contributes a nonnegative amount to the cut weight.

    For an arbitrary edge e, we consider the two branches of the if-then-else condition. If e crosses the cut between S and its complement (that is, there exist u ∈ S and v ∉ S with e = s(u, v)), its contribution is w(e), which is nonnegative by the hypothesis hw. Otherwise, its contribution is 0, and 0 ≤ 0 holds by reflexivity.

    lines 7–10

      intro e _
      split_ifs
      · exact hw e
      · rfl
Finset.sum_nonneg
A finite sum of nonnegative elements is nonnegative.

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

/-- Nonnegative edge weights yield a nonnegative cut weight for every vertex set. -/theorem simple_graph_cut_weight_nonneg {V : Type*} [Fintype V] [DecidableEq V]    (G : SimpleGraph V) [DecidableRel G.Adj] (w : G.edgeSet → ℝ) (hw : ∀ e, 0 ≤ w e) (S : Finset V) :    0 ≤ simple_graph_cut_weight G w S := by  unfold simple_graph_cut_weight  apply Finset.sum_nonneg  intro e _  split_ifs  · exact hw e  · rfl
See it in the graphDiscuss this resultChallenge it