greedy_max_cut_half_edges_lower_bound
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 thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
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.
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.
uses
greedy_cut_finset_boundobtain ⟨S, -, hS⟩ := greedy_cut_finset_bound G (Finset.univ : Finset V) use S
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.
uses
Finset.univ_product_univ,G.two_mul_card_edgeFinset,Finset.compl_eq_univ_sdiffrw [Finset.univ_product_univ] at hS rw [← G.two_mul_card_edgeFinset] at hS rw [Finset.compl_eq_univ_sdiff]
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.
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.
- In this formalization, cut edges are counted as ordered pairs (u, v) ∈ S × Sᶜ with u ∼ v. Since each undirected edge in the cut has exactly one endpoint in S and one in Sᶜ, this count equals the number of undirected cut edges. The bound |E(G)| ≤ 2 * |E(S, Sᶜ)| therefore states that the cut contains at least half of the edges of G.
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.
/-- 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