greedy_cut_finset_bound
For every finite set of vertices A in a simple graph G, there is a subset S ⊆ A such that the number of cut edges between S and A \ S is at least 1/4 of the ordered adjacent pairs in A × A.
Statement
theorem greedy_cut_finset_bound {V : Type*} [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (A : Finset V) : ∃ S : Finset V, S ⊆ A ∧ ((A ×ˢ A).filter (fun ⟨u, v⟩ => G.Adj u v)).card ≤ 4 * ((S ×ˢ (A \ S)).filter (fun ⟨u, v⟩ => G.Adj u v)).card
- Source
- step towards greedy_max_cut_half_edges_lower_bound
- Verified
- 11 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- card_filter_singleton_prodThe number of directed edges in {v} × S is the number of neighbors of v in S.
- card_filter_prod_singletonThe number of directed edges in S × {v} is the number of neighbors of v in S.
- Used by 1
- greedy_max_cut_half_edges_lower_boundEvery finite simple graph G has a subset of vertices S such that the number of cut edges between S and V \ S is at least half the total…
The proof, explained
The theorem is proved by induction on the finite set of vertices A using a greedy max-cut argument. In the base case A = ∅, the choice S = ∅ trivially works. In the inductive step, when a new vertex v is adjoined to A, we compare the number of neighbors of v in S with those in A \ S. By placing v greedily on whichever side has fewer neighbors, the directed cut gains at least half of the degree of v in A, which compensates for the twice-degree increase in the total directed edges of A × A.
The number of directed edges in (S ∪ {v}) × T equals the number of directed edges in S × T plus the number of neighbors of v in T, provided v ∉ S.
Since v ∉ S, the product (S ∪ {v}) × T partitions into the disjoint union of {v} × T and S × T. Filtering for graph adjacency preserves disjointness, so the cardinality of the union is the sum of the cardinalities. The adjacent pairs in {v} × T are precisely the neighbors of v in T.
uses
Finset.insert_eq,Finset.union_product,Finset.filter_union,Finset.disjoint_product,Finset.disjoint_singleton_left.mpr,Finset.disjoint_filter_filter,Finset.card_union_of_disjoint,card_filter_singleton_prod,add_commrw [Finset.insert_eq, Finset.union_product, Finset.filter_union] have hd : Disjoint ({v} ×ˢ T) (S ×ˢ T) := by rw [Finset.disjoint_product] left exact Finset.disjoint_singleton_left.mpr hv have hdf : Disjoint (({v} ×ˢ T).filter (fun ⟨u, w⟩ => G.Adj u w)) ((S ×ˢ T).filter (fun ⟨u, w⟩ => G.Adj u w)) := Finset.disjoint_filter_filter hd rw [Finset.card_union_of_disjoint hdf, card_filter_singleton_prod, add_comm]
The number of directed edges in S × (T ∪ {v}) equals the number of directed edges in S × T plus the number of neighbors of v in S, provided v ∉ T.
Analogously, because v ∉ T, the product S × (T ∪ {v}) decomposes into the disjoint union of S × {v} and S × T. Filtering for adjacency keeps them disjoint, and the edges in S × {v} correspond to the neighbors of v in S.
uses
Finset.insert_eq,Finset.product_union,Finset.filter_union,Finset.disjoint_product,Finset.disjoint_singleton_left.mpr,Finset.disjoint_filter_filter,Finset.card_union_of_disjoint,card_filter_prod_singleton,add_commrw [Finset.insert_eq, Finset.product_union, Finset.filter_union] have hd : Disjoint (S ×ˢ {v}) (S ×ˢ T) := by rw [Finset.disjoint_product] right exact Finset.disjoint_singleton_left.mpr hv have hdf : Disjoint ((S ×ˢ {v}).filter (fun ⟨u, w⟩ => G.Adj u w)) ((S ×ˢ T).filter (fun ⟨u, w⟩ => G.Adj u w)) := Finset.disjoint_filter_filter hd rw [Finset.card_union_of_disjoint hdf, card_filter_prod_singleton, add_comm]
The neighbors of v in A ∪ {v} are exactly the neighbors of v in A.
By extensionality, a vertex w is an adjacent neighbor in A ∪ {v} if and only if (w = v or w ∈ A) and v is adjacent to w. Since simple graphs have no loops, v cannot be adjacent to itself, eliminating the case w = v.
uses
Finset.mem_filter,Finset.mem_insert,Or.inrext w simp only [Finset.mem_filter, Finset.mem_insert] constructor · rintro ⟨rfl | hw, hadj⟩ · exact (G.irrefl hadj).elim · exact ⟨hw, hadj⟩ · rintro ⟨hw, hadj⟩ exact ⟨Or.inr hw, hadj⟩
Adding a vertex v ∉ A increases the directed edges in A × A by twice the number of neighbors of v in A.
Applying the insertion lemmas on the left and right decomposes (A ∪ {v}) × (A ∪ {v}) into the edges in A × A plus the edges from v into A ∪ {v} and from A into v. Since v has no self-loops, the neighbors in A ∪ {v} match those in A, giving twice the degree of v into A. Linear arithmetic simplifies the sum.
uses
greedy_cut_finset_bound_insert_left,greedy_cut_finset_bound_insert_right,greedy_cut_finset_bound_filter_insertrw [greedy_cut_finset_bound_insert_left G v A (insert v A) hv] rw [greedy_cut_finset_bound_insert_right G v A A hv] rw [greedy_cut_finset_bound_filter_insert G v A] omega
For any predicate p and subset S ⊆ A, the count of elements in A satisfying p is the sum of the counts in S and in A \ S.
The set A is the disjoint union of S and A \ S whenever S ⊆ A. Filtering this union preserves disjointness, so the cardinality of the filtered union is the sum of the cardinalities of the two filtered subsets.
uses
Finset.disjoint_sdiff,Finset.union_sdiff_of_subset,Finset.filter_union,Finset.card_union_of_disjoint,Finset.disjoint_filter_filterhave hd : Disjoint S (A \ S) := Finset.disjoint_sdiff have hu : S ∪ (A \ S) = A := Finset.union_sdiff_of_subset hS nth_rw 1 [← hu] rw [Finset.filter_union, Finset.card_union_of_disjoint (Finset.disjoint_filter_filter hd)]
If v ∉ A, then (A ∪ {v}) \ (S ∪ {v}) = A \ S.
An element x belongs to (A ∪ {v}) \ (S ∪ {v}) if and only if (x = v ∨ x ∈ A) and ¬(x = v ∨ x ∈ S). The negation forces x ≠ v, which eliminates x = v from the disjunction and leaves x ∈ A and x ∉ S.
uses
Finset.mem_sdiff,Finset.mem_insertext x simp only [Finset.mem_sdiff, Finset.mem_insert] aesop
If v ∉ S, then (A ∪ {v}) \ S = (A \ S) ∪ {v}.
An element x belongs to (A ∪ {v}) \ S if and only if (x = v ∨ x ∈ A) and x ∉ S. Because v ∉ S, this condition is equivalent to x = v ∨ (x ∈ A ∧ x ∉ S), which defines (A \ S) ∪ {v}.
uses
Finset.mem_sdiff,Finset.mem_insertext x simp only [Finset.mem_sdiff, Finset.mem_insert] aesop
The cut bound holds for the base case A = ∅.
Induction on finite sets. When A = ∅, we choose S = ∅ ⊆ ∅. There are no directed edges in ∅ × ∅ and none in ∅ × (∅ \ ∅), so 0 ≤ 4 · 0 holds trivially.
uses
Finset.induction_oninduction' A using Finset.induction_on with v A hv ih · use ∅ simp
Given S ⊆ A satisfying the induction hypothesis, the neighbors of v partition between S and A \ S, and the edge count in A ∪ {v} is expressed in terms of A.
We obtain S ⊆ A from the induction hypothesis. Since v ∉ A, v belongs to neither S nor A \ S. By greedy_cut_finset_bound_filter_sdiff, the neighbors of v in A partition into those in S and those in A \ S. By greedy_cut_finset_bound_card_insert_insert, adding v increases the directed edges in A × A by twice the degree of v into A.
uses
Finset.mem_sdiff.mp,greedy_cut_finset_bound_filter_sdiff,greedy_cut_finset_bound_card_insert_insert· rcases ih with ⟨S, hS, h_bound⟩ have hvS : v ∉ S := fun h => hv (hS h) have hvAS : v ∉ A \ S := fun h => hv (Finset.mem_sdiff.mp h).1 have h_split : (A.filter (fun w => G.Adj v w)).card = (S.filter (fun w => G.Adj v w)).card + ((A \ S).filter (fun w => G.Adj v w)).card := greedy_cut_finset_bound_filter_sdiff (fun w => G.Adj v w) A S hS have h_card_A : (((insert v A ×ˢ insert v A).filter (fun ⟨u, w⟩ => G.Adj u w)).card) = (((A ×ˢ A).filter (fun ⟨u, w⟩ => G.Adj u w)).card) + 2 * (A.filter (fun w => G.Adj v w)).card := greedy_cut_finset_bound_card_insert_insert G v A hv
If v has at least as many neighbors in A \ S as in S, placing v in S preserves the cut bound for A ∪ {v}.
We choose S ∪ {v} ⊆ A ∪ {v}. The new complement is (A ∪ {v}) \ (S ∪ {v}) = A \ S, and the cut edges from S ∪ {v} to A \ S increase by the neighbors of v in A \ S. Since these neighbors are at least half of all neighbors of v in A, 4 times this increase exceeds twice the degree of v into A, so the induction step closes by linear arithmetic.
uses
Finset.insert_subset_insert,greedy_cut_finset_bound_sdiff_insert_both,greedy_cut_finset_bound_insert_leftby_cases h_le : (S.filter (fun w => G.Adj v w)).card ≤ ((A \ S).filter (fun w => G.Adj v w)).card · use insert v S refine ⟨Finset.insert_subset_insert v hS, ?_⟩ rw [greedy_cut_finset_bound_sdiff_insert_both v A S hv] rw [greedy_cut_finset_bound_insert_left G v S (A \ S) hvS] omega
If v has more neighbors in S than in A \ S, keeping S unchanged preserves the cut bound for A ∪ {v}.
We retain S ⊆ A ∪ {v}, which places v into the complement (A ∪ {v}) \ S = (A \ S) ∪ {v}. The cut edges from S into the complement increase by the neighbors of v in S. Since this increase is more than half of the degree of v into A, 4 times the increase covers the 2 deg_A(v) additional edges in A × A, completing the proof by linear arithmetic.
uses
Finset.subset_insert,greedy_cut_finset_bound_sdiff_insert_left,greedy_cut_finset_bound_insert_right· use S refine ⟨hS.trans (Finset.subset_insert v A), ?_⟩ rw [greedy_cut_finset_bound_sdiff_insert_left v A S hvS] rw [greedy_cut_finset_bound_insert_right G v S (A \ S) hvAS] omega
add_comm- Addition is commutative: a + b = b + a.
card_filter_prod_singleton- The number of directed edges in S × {v} equals the number of neighbors of v in S.
card_filter_singleton_prod- The number of directed edges in {v} × S equals the number of neighbors of v in S.
Finset.card_union_of_disjoint- The cardinality of the union of two disjoint sets is the sum of their cardinalities: |s ∪ t| = |s| + |t| when s and t are disjoint.
Finset.disjoint_filter_filter- Subsets obtained by filtering disjoint sets by predicates are themselves disjoint.
Finset.disjoint_product- Two Cartesian products s × t and s' × t' are disjoint if and only if s and s' are disjoint or t and t' are disjoint.
Finset.disjoint_sdiff- A set s and a set difference t \ s are disjoint.
Finset.disjoint_singleton_left.mpr- A singleton {a} is disjoint from a set s if a ∉ s.
Finset.filter_union- Filtering a union by a predicate distributes over the union: {x ∈ s₁ ∪ s₂ | p x} = {x ∈ s₁ | p x} ∪ {x ∈ s₂ | p x}.
Finset.induction_on- Induction principle for finite sets: a property holds for all finite sets if it holds for ∅ and is preserved under adjoining a new element.
Finset.insert_eq- Inserting an element a into a finite set s is equal to {a} ∪ s.
Finset.insert_subset_insert- If s ⊆ t, then s ∪ {a} ⊆ t ∪ {a}.
Finset.mem_filter- An element belongs to a filtered set {x ∈ s | p x} if and only if it belongs to s and satisfies p.
Finset.mem_insert- An element belongs to s ∪ {b} if and only if it equals b or belongs to s.
Finset.mem_sdiff.mp- If x belongs to the set difference s \ t, then x ∈ s and x ∉ t.
Finset.product_union- The Cartesian product distributes over union on the right: s × (t ∪ t') = (s × t) ∪ (s × t').
Finset.subset_insert- Every set s is a subset of s ∪ {a}.
Finset.union_product- The Cartesian product distributes over union on the left: (s ∪ s') × t = (s × t) ∪ (s' × t).
Finset.union_sdiff_of_subset- If s ⊆ t, then s ∪ (t \ s) = t.
greedy_cut_finset_bound_card_insert_insert- Adding a new vertex v ∉ A increases the directed edges in A × A by twice the number of neighbors of v in A.
greedy_cut_finset_bound_filter_insert- The set of neighbors of v in A ∪ {v} is the same as in A, because simple graphs contain no self-loops.
greedy_cut_finset_bound_filter_sdiff- For any subset S ⊆ A, the count of elements in A satisfying p is the sum of the counts in S and in A \ S.
greedy_cut_finset_bound_insert_left- Inserting v ∉ S into the left side of S × T increases the directed edges by the number of neighbors of v in T.
greedy_cut_finset_bound_insert_right- Inserting v ∉ T into the right side of S × T increases the directed edges by the number of neighbors of v in S.
greedy_cut_finset_bound_sdiff_insert_both- If v ∉ A, then (A ∪ {v}) \ (S ∪ {v}) = A \ S.
greedy_cut_finset_bound_sdiff_insert_left- If v ∉ S, then (A ∪ {v}) \ S = (A \ S) ∪ {v}.
Or.inr- If proposition b holds, then the disjunction a ∨ b holds.
- The theorem counts ordered pairs of adjacent vertices (directed edges) rather than undirected edges; each undirected edge corresponds to two ordered pairs. Furthermore, the cut counts only directed pairs from S to A \ S (one direction), which accounts for the factor of 4 in the bound compared to the usual 1/2 factor for undirected cuts.
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.
theorem greedy_cut_finset_bound_insert_left {V : Type*} [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (v : V) (S T : Finset V) (hv : v ∉ S) : (((insert v S ×ˢ T).filter (fun ⟨u, w⟩ => G.Adj u w)).card) = (((S ×ˢ T).filter (fun ⟨u, w⟩ => G.Adj u w)).card) + (T.filter (fun w => G.Adj v w)).card := by rw [Finset.insert_eq, Finset.union_product, Finset.filter_union] have hd : Disjoint ({v} ×ˢ T) (S ×ˢ T) := by rw [Finset.disjoint_product] left exact Finset.disjoint_singleton_left.mpr hv have hdf : Disjoint (({v} ×ˢ T).filter (fun ⟨u, w⟩ => G.Adj u w)) ((S ×ˢ T).filter (fun ⟨u, w⟩ => G.Adj u w)) := Finset.disjoint_filter_filter hd rw [Finset.card_union_of_disjoint hdf, card_filter_singleton_prod, add_comm]theorem greedy_cut_finset_bound_insert_right {V : Type*} [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (v : V) (S T : Finset V) (hv : v ∉ T) : (((S ×ˢ insert v T).filter (fun ⟨u, w⟩ => G.Adj u w)).card) = (((S ×ˢ T).filter (fun ⟨u, w⟩ => G.Adj u w)).card) + (S.filter (fun w => G.Adj v w)).card := by rw [Finset.insert_eq, Finset.product_union, Finset.filter_union] have hd : Disjoint (S ×ˢ {v}) (S ×ˢ T) := by rw [Finset.disjoint_product] right exact Finset.disjoint_singleton_left.mpr hv have hdf : Disjoint ((S ×ˢ {v}).filter (fun ⟨u, w⟩ => G.Adj u w)) ((S ×ˢ T).filter (fun ⟨u, w⟩ => G.Adj u w)) := Finset.disjoint_filter_filter hd rw [Finset.card_union_of_disjoint hdf, card_filter_prod_singleton, add_comm]theorem greedy_cut_finset_bound_filter_insert {V : Type*} [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (v : V) (A : Finset V) : ((insert v A).filter (fun w => G.Adj v w)) = (A.filter (fun w => G.Adj v w)) := by ext w simp only [Finset.mem_filter, Finset.mem_insert] constructor · rintro ⟨rfl | hw, hadj⟩ · exact (G.irrefl hadj).elim · exact ⟨hw, hadj⟩ · rintro ⟨hw, hadj⟩ exact ⟨Or.inr hw, hadj⟩theorem greedy_cut_finset_bound_card_insert_insert {V : Type*} [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (v : V) (A : Finset V) (hv : v ∉ A) : (((insert v A ×ˢ insert v A).filter (fun ⟨u, w⟩ => G.Adj u w)).card) = (((A ×ˢ A).filter (fun ⟨u, w⟩ => G.Adj u w)).card) + 2 * (A.filter (fun w => G.Adj v w)).card := by rw [greedy_cut_finset_bound_insert_left G v A (insert v A) hv] rw [greedy_cut_finset_bound_insert_right G v A A hv] rw [greedy_cut_finset_bound_filter_insert G v A] omegatheorem greedy_cut_finset_bound_filter_sdiff {V : Type*} [DecidableEq V] (p : V → Prop) [DecidablePred p] (A S : Finset V) (hS : S ⊆ A) : (A.filter p).card = (S.filter p).card + ((A \ S).filter p).card := by have hd : Disjoint S (A \ S) := Finset.disjoint_sdiff have hu : S ∪ (A \ S) = A := Finset.union_sdiff_of_subset hS nth_rw 1 [← hu] rw [Finset.filter_union, Finset.card_union_of_disjoint (Finset.disjoint_filter_filter hd)]theorem greedy_cut_finset_bound_sdiff_insert_both {V : Type*} [DecidableEq V] (v : V) (A S : Finset V) (hv : v ∉ A) : (insert v A \ insert v S) = A \ S := by ext x simp only [Finset.mem_sdiff, Finset.mem_insert] aesoptheorem greedy_cut_finset_bound_sdiff_insert_left {V : Type*} [DecidableEq V] (v : V) (A S : Finset V) (hv : v ∉ S) : (insert v A \ S) = insert v (A \ S) := by ext x simp only [Finset.mem_sdiff, Finset.mem_insert] aesop/-- Greedy cut bound on any subset: for any finite subset A, there is S ⊆ A such that the number of cut edges between S and A \ S is at least 1/4 of the ordered adjacent pairs in A × A. -/theorem greedy_cut_finset_bound {V : Type*} [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (A : Finset V) : ∃ S : Finset V, S ⊆ A ∧ ((A ×ˢ A).filter (fun ⟨u, v⟩ => G.Adj u v)).card ≤ 4 * ((S ×ˢ (A \ S)).filter (fun ⟨u, v⟩ => G.Adj u v)).card := by induction' A using Finset.induction_on with v A hv ih · use ∅ simp · rcases ih with ⟨S, hS, h_bound⟩ have hvS : v ∉ S := fun h => hv (hS h) have hvAS : v ∉ A \ S := fun h => hv (Finset.mem_sdiff.mp h).1 have h_split : (A.filter (fun w => G.Adj v w)).card = (S.filter (fun w => G.Adj v w)).card + ((A \ S).filter (fun w => G.Adj v w)).card := greedy_cut_finset_bound_filter_sdiff (fun w => G.Adj v w) A S hS have h_card_A : (((insert v A ×ˢ insert v A).filter (fun ⟨u, w⟩ => G.Adj u w)).card) = (((A ×ˢ A).filter (fun ⟨u, w⟩ => G.Adj u w)).card) + 2 * (A.filter (fun w => G.Adj v w)).card := greedy_cut_finset_bound_card_insert_insert G v A hv by_cases h_le : (S.filter (fun w => G.Adj v w)).card ≤ ((A \ S).filter (fun w => G.Adj v w)).card · use insert v S refine ⟨Finset.insert_subset_insert v hS, ?_⟩ rw [greedy_cut_finset_bound_sdiff_insert_both v A S hv] rw [greedy_cut_finset_bound_insert_left G v S (A \ S) hvS] omega · use S refine ⟨hS.trans (Finset.subset_insert v A), ?_⟩ rw [greedy_cut_finset_bound_sdiff_insert_left v A S hvS] rw [greedy_cut_finset_bound_insert_right G v S (A \ S) hvAS] omega