three_token_k2n_domination_number_four
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
- token_graphThe k-token graph F_k(G) of a simple graph G has as vertices the k-subsets of V(G), with two k-subsets adjacent whenever their symmetric…
- simple_graph_domination_numberThe domination number gamma(G) of a finite simple graph G is the minimum cardinality of a dominating set of G.
- three_token_k2n_domination_number_four_leThe domination number of the 3-token graph F_3(K_{2,4}) of the complete bipartite graph K_{2,4} is at most 4.
- three_token_k2n_domination_number_four_geThe domination number of the 3-token graph F_3(K_{2,4}) of the complete bipartite graph K_{2,4} is at least 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.
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.
uses
le_antisymm,three_token_k2n_domination_number_four_le,three_token_k2n_domination_number_four_gesimple_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