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
- complete_graph_four_bipartite_frustrationThe bipartite frustration index of the complete graph K_4 on four vertices is equal to 2.
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