complete_graph_four_bipartite_frustration
The bipartite frustration index of the complete graph K_4 on four vertices is equal to 2.
Statement
theorem complete_graph_four_bipartite_frustration :
bipartite_frustration (SimpleGraph.completeGraph (Fin 4)) = 2- Related work
- arXiv:2204.00875
- Verified
- 12 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- bipartite_frustrationThe bipartite frustration index f(G) of a finite graph G is the minimum number of edges whose deletion makes G bipartite, or equivalently…
Read back from the Lean
The bipartite frustration of the complete graph on the vertex set Fin 4 is equal to 2, where the bipartite frustration of a finite simple graph $G = (V, E)$ is defined as the minimum, taken over all 2-colorings $c : V \to \mathrm{Bool}$, of the number of edges whose endpoints are assigned the same color by $c$.
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 bipartite frustration index measures the minimum number of monochromatic edges over all 2-colorings of a graph's vertices. For the complete graph K₄ on 4 vertices, there are only 2⁴ = 16 possible colorings, and the minimum is achieved by any partition into two sets of size 2, yielding 1 + 1 = 2 monochromatic edges. The proof delegates this finite exhaustive search directly to Lean's `decide` decision procedure.
The bipartite frustration index of the complete graph on 4 vertices is equal to 2. automation
The bipartite frustration index is defined as the minimum number of monochromatic edges over all possible 2-colorings (vertex cuts) c : Fin 4 → Bool. Since the vertex set has size 4, there are only 2⁴ = 16 possible colorings to evaluate. For a balanced 2-versus-2 coloring, the number of monochromatic edges is (2 choose 2) + (2 choose 2) = 2, while more unbalanced colorings produce 3 or 6 monochromatic edges. Because the domain is finite and the property is decidable, the `decide` tactic proves the equality by exhaustive computation.
decide
- The proof relies entirely on computational evaluation (`decide`) by exhausting all 16 candidate 2-colorings of the 4 vertices, without intermediate deduction steps.
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.
/-- The bipartite frustration index of K_4 is 2. -/theorem complete_graph_four_bipartite_frustration : bipartite_frustration (SimpleGraph.completeGraph (Fin 4)) = 2 := by decide