AFTD Auto-Formalizing Theoretical Domains

bipartite_frustration

deforiginal

The bipartite frustration index f(G) of a finite graph G is the minimum number of edges whose deletion makes G bipartite, or equivalently the minimum number of monochromatic edges over all 2-colorings of V.

Statement

def bipartite_frustration {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] : ℕ
Related work
folklore
Verified
11 Nov 2026
Axioms
none listed
Used by 1

Read back from the Lean

Given a finite type V with decidable equality and a simple graph G on V with decidable adjacency, bipartite_frustration G is defined as the minimum (infimum) over all 2-colorings c : V → Bool (with the constant function c = (fun _ => true) witnessing that Finset.univ is non-empty) of the number of edges e = s(u, v) of G whose endpoints have the same color under c (i.e., c u = c v).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- The frustration index (or bipartite edge deletion number) of a finite graph G: the minimum number of monochromatic edges over all 2-colorings of the vertices, equal to |E| - maxcut(G). -/
def bipartite_frustration {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] : ℕ := Finset.univ.inf' ⟨fun _ => true, Finset.mem_univ _⟩ fun c : V → Bool =>
    (G.edgeFinset.filter fun e =>
      Sym2.lift ⟨fun u v => c u == c v, fun _ _ => by dsimp; rw [Bool.beq_comm]⟩ e).card
See it in the graphDiscuss this resultChallenge it