AFTD Auto-Formalizing Theoretical Domains

greedy_cut_finset_bound

theoremverified

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
Used by 1

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.

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

    lines 5–12

    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_comm

      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]
  2. 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.

    lines 18–25

    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_comm

      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]
  3. 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.

    lines 30–37

    uses Finset.mem_filter, Finset.mem_insert, Or.inr

      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⟩
  4. 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.

    lines 43–46

    uses greedy_cut_finset_bound_insert_left, greedy_cut_finset_bound_insert_right, greedy_cut_finset_bound_filter_insert

      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]
      omega
  5. 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.

    lines 51–54

    uses Finset.disjoint_sdiff, Finset.union_sdiff_of_subset, Finset.filter_union, Finset.card_union_of_disjoint, Finset.disjoint_filter_filter

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

    lines 59–61

    uses Finset.mem_sdiff, Finset.mem_insert

      ext x
      simp only [Finset.mem_sdiff, Finset.mem_insert]
      aesop
  7. 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}.

    lines 66–68

    uses Finset.mem_sdiff, Finset.mem_insert

      ext x
      simp only [Finset.mem_sdiff, Finset.mem_insert]
      aesop
  8. 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.

    lines 76–78

    uses Finset.induction_on

      induction' A using Finset.induction_on with v A hv ih
      · use ∅
        simp
  9. 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.

    lines 79–87

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

    lines 88–93

    uses Finset.insert_subset_insert, greedy_cut_finset_bound_sdiff_insert_both, greedy_cut_finset_bound_insert_left

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

    lines 94–98

    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.

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

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