three_token_k2n_domination_number_four_le
The domination number of the 3-token graph F_3(K_{2,4}) of the complete bipartite graph K_{2,4} is at most 4.
Statement
theorem three_token_k2n_domination_number_four_le :
simple_graph_domination_number (token_graph (completeBipartiteGraph (Fin 2) (Fin 4)) 3) ≤ 4- Source
- step towards three_token_k2n_domination_number_four
- Verified
- 01 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- simple_graph_domination_numberThe domination number gamma(G) of a finite simple graph G is the minimum cardinality of a dominating set of G.
- 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_is_dominatingA subset S of vertices in a simple graph G is a dominating set if every vertex of G is in S or is adjacent to a vertex in S.
- Used by 1
- three_token_k2n_domination_number_fourThe domination number of the 3-token graph F_3(K_{2,4}) of the complete bipartite graph K_{2,4} is 4.
The proof, explained
The proof explicitly constructs a dominating set $S = \{v_1, v_2, v_3, v_4\}$ of size 4 in the 3-token graph $F_3(K_{2,4})$. Since the graph has only $\binom{6}{3} = 20$ vertices, Lean verifies by exhaustive computation that every vertex is in $S$ or adjacent to a vertex in $S$. The result then follows from the definition of the domination number as the infimum of the sizes of dominating sets.
Define a candidate dominating set $S = \\{v_1, v_2, v_3, v_4\\}$ consisting of four vertices in the token graph.
Vertices of the 3-token graph $F_3(K_{2,4})$ are 3-element subsets of the 6-element vertex set $\\mathrm{Fin}\\,2 \\oplus \\mathrm{Fin}\\,4$. We define four explicit 3-element subsets $v_1, v_2, v_3, v_4$ (each verified to have cardinality 3 by Lean's `decide` tactic) and gather them into the subset $S = \\{v_1, v_2, v_3, v_4\\}$.
let v1 : { s : Finset (Fin 2 ⊕ Fin 4) // s.card = 3 } := ⟨{Sum.inl 0, Sum.inl 1, Sum.inr 1}, by decide⟩ let v2 : { s : Finset (Fin 2 ⊕ Fin 4) // s.card = 3 } := ⟨{Sum.inl 0, Sum.inr 1, Sum.inr 2}, by decide⟩ let v3 : { s : Finset (Fin 2 ⊕ Fin 4) // s.card = 3 } := ⟨{Sum.inl 1, Sum.inr 0, Sum.inr 3}, by decide⟩ let v4 : { s : Finset (Fin 2 ⊕ Fin 4) // s.card = 3 } := ⟨{Sum.inr 0, Sum.inr 2, Sum.inr 3}, by decide⟩ let S : Finset { s : Finset (Fin 2 ⊕ Fin 4) // s.card = 3 } := {v1, v2, v3, v4}
The set $S$ is a dominating set in $F_3(K_{2,4})$. automation
By definition, $S$ dominates if every vertex $v$ of the token graph is either in $S$ or adjacent to some vertex in $S$. We introduce a generic vertex $v$, expand the definitions of $S$, each $v_i$, the token graph adjacency relation, and the complete bipartite graph $K_{2,4}$, and revert $v$. This produces a universally quantified proposition over the finite vertex set (of size $\\binom{6}{3} = 20$), which Lean verifies exhaustively using `decide`.
have hdom : simple_graph_is_dominating (token_graph (completeBipartiteGraph (Fin 2) (Fin 4)) 3) (S : Set _) := by intro v dsimp only [S, v1, v2, v3, v4] unfold token_graph completeBipartiteGraph dsimp only revert v decide
The set $S$ has cardinality 4. automation
Because the four vertices $v_1, v_2, v_3, v_4$ are pairwise distinct, the set $S$ has exactly 4 elements; this is verified by direct computation with `decide`.
have hc : S.card = 4 := by decide
The domination number of $F_3(K_{2,4})$ is at most 4.
The domination number of a graph is defined as the infimum of the cardinalities of all its dominating sets. Because $S$ is a dominating set of size 4, the number 4 belongs to this set of cardinalities, so `Nat.sInf_le` yields that the domination number is at most 4.
uses
Nat.sInf_leexact Nat.sInf_le ⟨S, hdom, hc⟩
Nat.sInf_le- For any set $s \\subseteq \\mathbb{N}$ and any element $m \\in s$, the infimum $\\operatorname{sInf} s$ is at most $m$.
- The domination property (line 15) and set cardinalities (lines 4–7, 16) are proved by finite exhaustive computation via Lean's `decide` tactic over the 20 vertices of the 3-token graph.
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 domination number of the 3-token graph F_3(K_{2,4}) is at most 4. -/theorem three_token_k2n_domination_number_four_le : simple_graph_domination_number (token_graph (completeBipartiteGraph (Fin 2) (Fin 4)) 3) ≤ 4 := by let v1 : { s : Finset (Fin 2 ⊕ Fin 4) // s.card = 3 } := ⟨{Sum.inl 0, Sum.inl 1, Sum.inr 1}, by decide⟩ let v2 : { s : Finset (Fin 2 ⊕ Fin 4) // s.card = 3 } := ⟨{Sum.inl 0, Sum.inr 1, Sum.inr 2}, by decide⟩ let v3 : { s : Finset (Fin 2 ⊕ Fin 4) // s.card = 3 } := ⟨{Sum.inl 1, Sum.inr 0, Sum.inr 3}, by decide⟩ let v4 : { s : Finset (Fin 2 ⊕ Fin 4) // s.card = 3 } := ⟨{Sum.inr 0, Sum.inr 2, Sum.inr 3}, by decide⟩ let S : Finset { s : Finset (Fin 2 ⊕ Fin 4) // s.card = 3 } := {v1, v2, v3, v4} have hdom : simple_graph_is_dominating (token_graph (completeBipartiteGraph (Fin 2) (Fin 4)) 3) (S : Set _) := by intro v dsimp only [S, v1, v2, v3, v4] unfold token_graph completeBipartiteGraph dsimp only revert v decide have hc : S.card = 4 := by decide exact Nat.sInf_le ⟨S, hdom, hc⟩