AFTD Auto-Formalizing Theoretical Domains

simple_graph_cut_weight_empty

theoremverified

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

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.

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

    line 4

    uses two_le_simple_graph_tree_estimate

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

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

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