AFTD Auto-Formalizing Theoretical Domains

greedy_max_cut_half_edges_lower_bound

theoremverifiedformalization

Every 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 number of edges in G: G.edgeFinset.card ≤ 2 * ((S ×ˢ Sᶜ).filter (fun ⟨u, v⟩ => G.Adj u v)).card.

Statement

theorem greedy_max_cut_half_edges_lower_bound {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) [DecidableRel G.Adj] :
    ∃ S : Finset V, G.edgeFinset.card ≤ 2 * ((S ×ˢ Sᶜ).filter (fun ⟨u, v⟩ => G.Adj u v)).card
Formalizes
Erdős (1965), 'On even subgraphs of graphs'; Vazirani (2001), Approximation Algorithms, Theorem 2.1
Verified
11 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
  • 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.
  • greedy_cut_finset_boundFor 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…
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.

Read back from the Lean

For every finite type $V$ with decidable equality and every simple graph $G$ on $V$ with decidable adjacency relation, there exists a finset $S \subseteq V$ such that the number of edges of $G$ is at most twice the number of ordered pairs $(u, v) \in S \times S^c$ such that $u$ and $v$ are adjacent in $G$.

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 proof applies the greedy cut theorem (`greedy_cut_finset_bound`) to the universal vertex set V, obtaining a subset S ⊆ V such that the number of directed edges in the whole graph is at most 4 times the number of directed cut edges between S and V \ S. By the handshake lemma (`G.two_mul_card_edgeFinset`), the total number of directed edges equals 2 * |E(G)|. Rewriting the complement Sᶜ as V \ S and dividing the resulting inequality 2 * |E(G)| ≤ 4 * |E(S, Sᶜ)| by 2 completes the proof.

  1. There exists a vertex subset S ⊆ V satisfying the greedy cut inequality on the whole graph.

    Applying the greedy cut lemma `greedy_cut_finset_bound` to the universal vertex set A = Finset.univ provides a subset S ⊆ V such that the number of directed edges in V × V is at most 4 times the number of directed cut edges from S to V \ S. We choose this S as our witness for the existential goal.

    lines 5–6

    uses greedy_cut_finset_bound

      obtain ⟨S, -, hS⟩ := greedy_cut_finset_bound G (Finset.univ : Finset V)
      use S
  2. The greedy cut hypothesis simplifies to 2 * |E(G)| ≤ 4 * |E(S, V \ S)|, matching the form of the goal.

    By `Finset.univ_product_univ`, the product univ ×ˢ univ simplifies to univ, so the left-hand side of hypothesis hS counts all ordered adjacent vertex pairs. By `G.two_mul_card_edgeFinset`, this count equals twice the total number of edges, 2 * |E(G)|. Rewriting the complement Sᶜ in the goal as Finset.univ \ S via `Finset.compl_eq_univ_sdiff` aligns the goal's cut edge set with that in hS.

    lines 7–9

    uses Finset.univ_product_univ, G.two_mul_card_edgeFinset, Finset.compl_eq_univ_sdiff

      rw [Finset.univ_product_univ] at hS
      rw [← G.two_mul_card_edgeFinset] at hS
      rw [Finset.compl_eq_univ_sdiff]
  3. The number of edges in G is at most twice the number of cut edges: |E(G)| ≤ 2 * |E(S, Sᶜ)|.

    We establish a local arithmetic lemma `h_arith` asserting that for all natural numbers a and b, 2 * a ≤ 4 * b implies a ≤ 2 * b using linear arithmetic (`linarith`). Applying this to hS with a = |E(G)| and b = |E(S, V \ S)| completes the proof.

    lines 10–13

      have h_arith : ∀ a b : ℕ, 2 * a ≤ 4 * b → a ≤ 2 * b := by
        intro a b h
        linarith
      exact h_arith _ _ hS
greedy_cut_finset_bound
For any finite subset of vertices A in a graph G, there exists a subset S ⊆ A such that the number of directed edges with both endpoints in A is at most 4 times the number of directed cut edges from S to A \ S.
Finset.univ_product_univ
The Cartesian product of the universal finite set with itself is the universal finite set of pairs.
G.two_mul_card_edgeFinset
Twice the number of undirected edges of G equals the number of ordered pairs of adjacent vertices in G.
Finset.compl_eq_univ_sdiff
The complement of a finite set S in a finite type equals the universal set minus S.

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

/-- Every finite simple graph has a cut containing at least half of its edges. -/theorem greedy_max_cut_half_edges_lower_bound {V : Type*} [Fintype V] [DecidableEq V]    (G : SimpleGraph V) [DecidableRel G.Adj] :    ∃ S : Finset V, G.edgeFinset.card ≤ 2 * ((S ×ˢ Sᶜ).filter (fun ⟨u, v⟩ => G.Adj u v)).card := by  obtain ⟨S, -, hS⟩ := greedy_cut_finset_bound G (Finset.univ : Finset V)  use S  rw [Finset.univ_product_univ] at hS  rw [← G.two_mul_card_edgeFinset] at hS  rw [Finset.compl_eq_univ_sdiff]  have h_arith : ∀ a b : ℕ, 2 * a ≤ 4 * b → a ≤ 2 * b := by    intro a b h    linarith  exact h_arith _ _ hS
See it in the graphDiscuss this resultChallenge it