AFTD Auto-Formalizing Theoretical Domains

complete_graph_four_bipartite_frustration

theoremverifiedoriginal

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.

  1. 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.

    line 4

      decide

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

/-- The bipartite frustration index of K_4 is 2. -/theorem complete_graph_four_bipartite_frustration :    bipartite_frustration (SimpleGraph.completeGraph (Fin 4)) = 2 := by  decide
See it in the graphDiscuss this resultChallenge it