AFTD Auto-Formalizing Theoretical Domains

three_token_k2n_domination_number_four

theoremverifiedoriginal

The domination number of the 3-token graph F_3(K_{2,4}) of the complete bipartite graph K_{2,4} is 4.

Statement

theorem three_token_k2n_domination_number_four :
    simple_graph_domination_number (token_graph (completeBipartiteGraph (Fin 2) (Fin 4)) 3) = 4
Related work
arXiv:2610.28936, Section 5
Verified
01 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4

Read back from the Lean

The domination number of the 3-token graph of the complete bipartite graph $K_{2, 4}$ (with vertex set Fin 2 ⊕ Fin 4) equals 4. Here: - The complete bipartite graph has parts of size 2 (Fin 2) and 4 (Fin 4). - The 3-token graph of a graph $G$ is the simple graph whose vertices are the 3-element subsets (Finset) of the vertices of $G$, with two subsets adjacent if and only if their symmetric difference is of the form $\{u, v\}$ for some edge $uv$ of $G$. - A set of vertices $S$ is dominating in a graph if every vertex is in $S$ or adjacent to a vertex in $S$. - The domination number of a finite simple graph is the infimum in $\mathbb{N}$ of the cardinalities of its dominating sets.

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 establishes that the domination number of the 3-token graph F_3(K_{2,4}) is 4 by combining separate upper and lower bounds. Applying antisymmetry of inequality (`le_antisymm`) to the results that the domination number is at most 4 and at least 4 immediately yields the exact value.

  1. The domination number of the 3-token graph F_3(K_{2,4}) is equal to 4.

    The equality is deduced directly by antisymmetry of the order ≤ (`le_antisymm`), combining the previously established upper bound (`three_token_k2n_domination_number_four_le`) showing that the domination number is at most 4 and lower bound (`three_token_k2n_domination_number_four_ge`) showing that it is at least 4.

    line 3

    uses le_antisymm, three_token_k2n_domination_number_four_le, three_token_k2n_domination_number_four_ge

        simple_graph_domination_number (token_graph (completeBipartiteGraph (Fin 2) (Fin 4)) 3) = 4 := le_antisymm three_token_k2n_domination_number_four_le three_token_k2n_domination_number_four_ge
le_antisymm
In any partial order, if a ≤ b and b ≤ a, then a = b.
three_token_k2n_domination_number_four_le
The domination number of the 3-token graph of K_{2,4} is at most 4.
three_token_k2n_domination_number_four_ge
The domination number of the 3-token graph of K_{2,4} is at least 4.

Written by a model (gemini-3.8-flash) from the Lean source alone (no goal states were available). Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

/-- The domination number of F_3(K_{2,4}) is 4. -/theorem three_token_k2n_domination_number_four :    simple_graph_domination_number (token_graph (completeBipartiteGraph (Fin 2) (Fin 4)) 3) = 4 := le_antisymm three_token_k2n_domination_number_four_le three_token_k2n_domination_number_four_ge
See it in the graphDiscuss this resultChallenge it