simple_graph_cut_weight_empty
In any simple graph G on a finite type V with decidable equality and decidable adjacency, with edge weighting w : G.edgeSet → ℝ, the cut weight simple_graph_cut_weight G w ∅ of the empty vertex set is zero.
Statement
theorem simple_graph_cut_weight_empty {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (w : G.edgeSet → ℝ) : simple_graph_cut_weight G w ∅ = 0
- Source
- folklore
- Verified
- 09 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- 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…
- two_le_simple_graph_tree_estimateThe tree estimate is at least 2.
Read back from the Lean
For any finite type V with decidable equality, any simple graph G on V with decidable adjacency, and any edge-weight function w : G.edgeSet → ℝ, the cut weight of the empty set of vertices, simple_graph_cut_weight G w ∅, equals 0.
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 the empty set of vertices is by definition the sum of edge weights over all edges connecting a vertex in ∅ to a vertex outside ∅. Since the empty set contains no vertices, no edge can satisfy this condition, so every summand is zero. Unfolding the definition reduces the expression to a finite sum of zeros, which simplifies immediately to zero.
The cut weight of the empty set of vertices is zero: simple_graph_cut_weight G w ∅ = 0. automation
Unfolding the definition of `simple_graph_cut_weight`, the cut weight across a vertex subset S is defined as the sum over all edges e of w(e) when e has one endpoint in S and one outside S, and 0 otherwise. For S = ∅, the condition that there exists an endpoint u ∈ ∅ is vacuously false for every edge. Each term in the sum therefore reduces to 0, and the sum of zeros over the finite edge set is 0.
uses
two_le_simple_graph_tree_estimatesimple_graph_cut_weight G w ∅ = 0 := by first | exact two_le_simple_graph_tree_estimate | (apply two_le_simple_graph_tree_estimate <;> assumption) | (apply two_le_simple_graph_tree_estimate <;> simp_all) | simpa using two_le_simple_graph_tree_estimate | (simp only [simple_graph_cut_weight] at *; first | exact two_le_simple_graph_tree_estimate | (apply two_le_simple_graph_tree_estimate <;> assumption) | (apply two_le_simple_graph_tree_estimate <;> simp_all) | simpa using two_le_simple_graph_tree_estimate)
two_le_simple_graph_tree_estimate- For any finite simple graph T with decidable equality and adjacency, the tree estimate of T is at least 2.
- The lemma `two_le_simple_graph_tree_estimate` is an artifact of an automated search block (`first | ... | simpa using ...`); it is mathematically irrelevant and unused by the simplifier, which closes the goal entirely by evaluating the sum of zeros.
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.
/-- The cut weight of the empty set of vertices is zero. -/theorem simple_graph_cut_weight_empty {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (w : G.edgeSet → ℝ) : simple_graph_cut_weight G w ∅ = 0 := by first | exact two_le_simple_graph_tree_estimate | (apply two_le_simple_graph_tree_estimate <;> assumption) | (apply two_le_simple_graph_tree_estimate <;> simp_all) | simpa using two_le_simple_graph_tree_estimate | (simp only [simple_graph_cut_weight] at *; first | exact two_le_simple_graph_tree_estimate | (apply two_le_simple_graph_tree_estimate <;> assumption) | (apply two_le_simple_graph_tree_estimate <;> simp_all) | simpa using two_le_simple_graph_tree_estimate)