simple_graph_cut_weight_nonneg
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.
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.
uses
Finset.sum_nonnegunfold simple_graph_cut_weight apply Finset.sum_nonneg
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.
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
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.
/-- 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