three_token_star_domination_number_four
The domination number of the 3-token graph of the star graph SimpleGraph.starGraph (none : Option (Fin 4)) is 3.
Statement
theorem three_token_star_domination_number_four :
simple_graph_domination_number (token_graph (SimpleGraph.starGraph (none : Option (Fin 4))) 3) = 3- Formalizes
- arXiv:2611.11191, Subsection 4.4
- Verified
- 11 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- 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.
- simple_graph_domination_numberThe domination number gamma(G) of a finite simple graph G is the minimum cardinality of a dominating set of G.
Read back from the Lean
The domination number of the 3-token graph of the star graph on Option (Fin 4) (the star graph $K_{1, 4}$ with 5 vertices, centered at none) is equal to 3.
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 domination number of the 3-token graph of the 5-vertex star graph K_{1,4} is determined to be 3 by proving matching upper and lower bounds. For the upper bound, an explicit 3-element set of vertices S = {v₁, v₂, v₃} is exhibited and verified by finite exhaustion to be a dominating set. For the lower bound, an exhaustive check confirms that no subset of size at most 2 can dominate the graph, so any minimal dominating set must have size at least 3. Combining both inequalities via antisymmetry shows the domination number is exactly 3.
Three 3-element subsets v₁, v₂, v₃ of the 5-vertex star graph are defined and gathered into a candidate set S = {v₁, v₂, v₃}.
The vertices of the 3-token graph are subsets of size 3 of Option (Fin 4). Three such vertices are defined explicitly: v₁ = {none, some 0, some 1}, v₂ = {some 0, some 2, some 3}, and v₃ = {some 1, some 2, some 3}. Each is checked to have cardinality 3 by decidability (`decide`), and their collection is packaged as the finite set S.
def three_token_star_domination_number_four_v1 : { s : Finset (Option (Fin 4)) // s.card = 3 } := ⟨{(none : Option (Fin 4)), some 0, some 1}, by decide⟩ def three_token_star_domination_number_four_v2 : { s : Finset (Option (Fin 4)) // s.card = 3 } := ⟨{some 0, some 2, some 3}, by decide⟩ def three_token_star_domination_number_four_v3 : { s : Finset (Option (Fin 4)) // s.card = 3 } := ⟨{some 1, some 2, some 3}, by decide⟩ def three_token_star_domination_number_four_S : Finset { s : Finset (Option (Fin 4)) // s.card = 3 } := {three_token_star_domination_number_four_v1, three_token_star_domination_number_four_v2, three_token_star_domination_number_four_v3}
S is a dominating set in the 3-token graph. automation
To show that S is dominating, we consider an arbitrary vertex v (a 3-element subset). After unfolding the definitions of the token graph and the star graph, Lean's `decide` tactic checks exhaustively that every vertex in the 3-token graph is either in S or adjacent to an element of S via a valid token move along an edge of the star graph.
theorem three_token_star_domination_number_four_le : simple_graph_domination_number (token_graph (SimpleGraph.starGraph (none : Option (Fin 4))) 3) ≤ 3 := by have hdom : simple_graph_is_dominating (token_graph (SimpleGraph.starGraph (none : Option (Fin 4))) 3) (three_token_star_domination_number_four_S : Set _) := by intro v dsimp only [three_token_star_domination_number_four_S, three_token_star_domination_number_four_v1, three_token_star_domination_number_four_v2, three_token_star_domination_number_four_v3] unfold token_graph SimpleGraph.starGraph dsimp only revert v decide
The domination number of the 3-token graph is at most 3.
The cardinality of S is verified to be 3 by `decide`. Since S is a dominating set of size 3, the infimum of the cardinalities of all dominating sets is at most 3 by `Nat.sInf_le`.
uses
Nat.sInf_lehave hc : three_token_star_domination_number_four_S.card = 3 := by decide exact Nat.sInf_le ⟨three_token_star_domination_number_four_S, hdom, hc⟩
No set of at most 2 vertices is a dominating set. automation
After unfolding the definitions of a dominating set, the token graph, and the star graph, the `decide` tactic exhaustively tests all subsets of vertices of size at most 2 and confirms that none of them dominates every vertex.
set_option maxRecDepth 2000000 in theorem three_token_star_domination_number_four_no_dom_two : ∀ S : Finset { s : Finset (Option (Fin 4)) // s.card = 3 }, S.card ≤ 2 → ¬ simple_graph_is_dominating (token_graph (SimpleGraph.starGraph (none : Option (Fin 4))) 3) (S : Set _) := by unfold simple_graph_is_dominating token_graph SimpleGraph.starGraph dsimp only decide
The set of cardinalities of dominating sets is nonempty.
To apply properties of the infimum, we demonstrate that a dominating set exists. The universal set `Finset.univ` containing all 10 vertices is trivially dominating because every vertex belongs to it by `Finset.mem_univ`.
uses
Finset.mem_univtheorem three_token_star_domination_number_four_ge : 3 ≤ simple_graph_domination_number (token_graph (SimpleGraph.starGraph (none : Option (Fin 4))) 3) := by unfold simple_graph_domination_number have hne : {k | ∃ S : Finset { s : Finset (Option (Fin 4)) // s.card = 3 }, simple_graph_is_dominating (token_graph (SimpleGraph.starGraph (none : Option (Fin 4))) 3) ↑S ∧ S.card = k}.Nonempty := by use (Finset.univ : Finset { s : Finset (Option (Fin 4)) // s.card = 3 }).card refine ⟨Finset.univ, ?_, rfl⟩ intro v left exact Finset.mem_univ v
The domination number of the 3-token graph is at least 3.
Because the set of dominating set sizes is nonempty, `Nat.sInf_mem` guarantees that the infimum is attained by some dominating set S. If its size were strictly less than 3, then by `not_le.mp` and `Nat.le_of_lt_succ` we would have |S| ≤ 2, contradicting `three_token_star_domination_number_four_no_dom_two`. Thus, the infimum must be at least 3.
uses
Nat.sInf_mem,Nat.le_of_lt_succ,not_le.mp,three_token_star_domination_number_four_no_dom_twohave hmem := Nat.sInf_mem hne dsimp at hmem rcases hmem with ⟨S, hdom, hcard⟩ rw [← hcard] by_contra hlt have hle : S.card ≤ 2 := Nat.le_of_lt_succ (not_le.mp hlt) exact three_token_star_domination_number_four_no_dom_two S hle hdom
The upper and lower bounds match, establishing that the domination number is 3.
Combining the upper bound of 3 (`three_token_star_domination_number_four_le`) and the lower bound of 3 (`three_token_star_domination_number_four_ge`) via antisymmetry of partial orders (`le_antisymm`) proves the domination number is exactly 3.
uses
le_antisymm,three_token_star_domination_number_four_le,three_token_star_domination_number_four_ge/-- The domination number of the 3-token graph of the star graph S_4 is 3. -/ theorem three_token_star_domination_number_four : simple_graph_domination_number (token_graph (SimpleGraph.starGraph (none : Option (Fin 4))) 3) = 3 := le_antisymm three_token_star_domination_number_four_le three_token_star_domination_number_four_ge
le_antisymm- In a partial order, if a ≤ b and b ≤ a, then a = b.
Nat.le_of_lt_succ- If a natural number is strictly less than n + 1, then it is less than or equal to n.
Nat.sInf_le- If a natural number belongs to a set of natural numbers, then the infimum of the set is at most that number.
Nat.sInf_mem- The infimum of any nonempty set of natural numbers belongs to that set (a nonempty set of natural numbers attains its minimum).
not_le.mp- If a natural number is not less than or equal to another, it is strictly greater.
Finset.mem_univ- Every element of a finite type is a member of its universal finite set.
three_token_star_domination_number_four_le- The domination number of the 3-token graph of the star graph on 5 vertices is at most 3.
three_token_star_domination_number_four_ge- The domination number of the 3-token graph of the star graph on 5 vertices is at least 3.
three_token_star_domination_number_four_no_dom_two- No set of at most 2 vertices is a dominating set in the 3-token graph of the star graph on 5 vertices.
- The base graph SimpleGraph.starGraph (none : Option (Fin 4)) is the star graph on 5 vertices: a central hub `none` and 4 leaves `some 0`, `some 1`, `some 2`, and `some 3`. Its 3-token graph has vertices corresponding to the 10 subsets of size 3.
- Both the verification that S dominates the graph (lines 17–27) and the proof that no set of size at most 2 is dominating (lines 31–38) are delegated to Lean's `decide` tactic, which exhaustively checks all vertices and candidate subsets by finite computation.
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.
def three_token_star_domination_number_four_v1 : { s : Finset (Option (Fin 4)) // s.card = 3 } := ⟨{(none : Option (Fin 4)), some 0, some 1}, by decide⟩def three_token_star_domination_number_four_v2 : { s : Finset (Option (Fin 4)) // s.card = 3 } := ⟨{some 0, some 2, some 3}, by decide⟩def three_token_star_domination_number_four_v3 : { s : Finset (Option (Fin 4)) // s.card = 3 } := ⟨{some 1, some 2, some 3}, by decide⟩def three_token_star_domination_number_four_S : Finset { s : Finset (Option (Fin 4)) // s.card = 3 } := {three_token_star_domination_number_four_v1, three_token_star_domination_number_four_v2, three_token_star_domination_number_four_v3}theorem three_token_star_domination_number_four_le : simple_graph_domination_number (token_graph (SimpleGraph.starGraph (none : Option (Fin 4))) 3) ≤ 3 := by have hdom : simple_graph_is_dominating (token_graph (SimpleGraph.starGraph (none : Option (Fin 4))) 3) (three_token_star_domination_number_four_S : Set _) := by intro v dsimp only [three_token_star_domination_number_four_S, three_token_star_domination_number_four_v1, three_token_star_domination_number_four_v2, three_token_star_domination_number_four_v3] unfold token_graph SimpleGraph.starGraph dsimp only revert v decide have hc : three_token_star_domination_number_four_S.card = 3 := by decide exact Nat.sInf_le ⟨three_token_star_domination_number_four_S, hdom, hc⟩set_option maxRecDepth 2000000 intheorem three_token_star_domination_number_four_no_dom_two : ∀ S : Finset { s : Finset (Option (Fin 4)) // s.card = 3 }, S.card ≤ 2 → ¬ simple_graph_is_dominating (token_graph (SimpleGraph.starGraph (none : Option (Fin 4))) 3) (S : Set _) := by unfold simple_graph_is_dominating token_graph SimpleGraph.starGraph dsimp only decidetheorem three_token_star_domination_number_four_ge : 3 ≤ simple_graph_domination_number (token_graph (SimpleGraph.starGraph (none : Option (Fin 4))) 3) := by unfold simple_graph_domination_number have hne : {k | ∃ S : Finset { s : Finset (Option (Fin 4)) // s.card = 3 }, simple_graph_is_dominating (token_graph (SimpleGraph.starGraph (none : Option (Fin 4))) 3) ↑S ∧ S.card = k}.Nonempty := by use (Finset.univ : Finset { s : Finset (Option (Fin 4)) // s.card = 3 }).card refine ⟨Finset.univ, ?_, rfl⟩ intro v left exact Finset.mem_univ v have hmem := Nat.sInf_mem hne dsimp at hmem rcases hmem with ⟨S, hdom, hcard⟩ rw [← hcard] by_contra hlt have hle : S.card ≤ 2 := Nat.le_of_lt_succ (not_le.mp hlt) exact three_token_star_domination_number_four_no_dom_two S hle hdom/-- The domination number of the 3-token graph of the star graph S_4 is 3. -/theorem three_token_star_domination_number_four : simple_graph_domination_number (token_graph (SimpleGraph.starGraph (none : Option (Fin 4))) 3) = 3 := le_antisymm three_token_star_domination_number_four_le three_token_star_domination_number_four_ge