three_token_star_domination_number_three_le
The domination number of the 3-token graph of the star graph SimpleGraph.starGraph (none : Option (Fin 3)) is at most 1.
Statement
theorem three_token_star_domination_number_three_le :
simple_graph_domination_number (token_graph (SimpleGraph.starGraph (none : Option (Fin 3))) 3) ≤ 1- Source
- 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.
- Used by 1
- three_token_star_domination_number_threeThe domination number of the 3-token graph of the star graph SimpleGraph.starGraph (none : Option (Fin 3)) is 1.
Read back from the Lean
The domination number of the 3-token graph of the star graph on Option (Fin 3) centered at none is at most 1.
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 a graph is the minimum cardinality of a dominating set. For the star graph $S_3$ on 4 vertices (the center $\operatorname{none}$ and 3 leaves), the vertices of the 3-token graph are the 3-element subsets of vertices. The singleton set $S = \{v_1\}$ containing the 3-subset of all leaves dominates the graph because every other 3-subset contains the center and two leaves, differing from $v_1$ by replacing one leaf with the adjacent center. Lean verifies this domination property by exhaustive evaluation (`decide`) over all $\binom{4}{3} = 4$ vertices, yielding a dominating set of size 1 and showing the domination number is at most 1.
Define the vertex $v_1 = \{\operatorname{some} 0, \operatorname{some} 1, \operatorname{some} 2\}$ and the candidate dominating set $S = \{v_1\}$.
The vertices of the 3-token graph are 3-element subsets of the 4-element vertex set of the star graph (consisting of the central vertex $\operatorname{none}$ and three leaves $\operatorname{some} 0, \operatorname{some} 1, \operatorname{some} 2$). We choose $v_1$ to be the subset of all three leaves (verified to have cardinality 3 by `decide`), and let $S$ be the singleton set containing $v_1$.
let v1 : { s : Finset (Option (Fin 3)) // s.card = 3 } := ⟨{some 0, some 1, some 2}, by decide⟩ let S : Finset { s : Finset (Option (Fin 3)) // s.card = 3 } := {v1}
The singleton set $S$ is a dominating set in the 3-token graph.
By definition, $S$ is dominating if every vertex $v$ of the 3-token graph is either in $S$ or adjacent to an element of $S$. We introduce an arbitrary vertex $v$, substitute the definitions of $S$ and $v_1$, and unfold the definitions of the star graph and the token graph (in which two 3-subsets are adjacent if their symmetric difference is an edge of the underlying star graph). Re-quantifying over $v$ yields a decidable statement over a finite domain of $\binom{4}{3} = 4$ vertices, which `decide` verifies by exhaustively checking each case.
have hdom : simple_graph_is_dominating (token_graph (SimpleGraph.starGraph (none : Option (Fin 3))) 3) (S : Set _) := by intro v dsimp only [S, v1] unfold token_graph SimpleGraph.starGraph dsimp only revert v decide
The set $S$ has cardinality 1.
Because $S = \{v_1\}$ is a singleton finset, its cardinality is 1, which is verified directly by computation via `decide`.
have hc : S.card = 1 := by decide
The domination number of the 3-token graph is at most 1.
The domination number is defined as the infimum of the cardinalities of all dominating sets. The singleton set $S$, together with its domination proof and cardinality 1, witnesses that 1 belongs to the set of sizes of dominating sets. Applying `Nat.sInf_le` concludes that the infimum of this set is at most 1.
uses
Nat.sInf_leexact Nat.sInf_le ⟨S, hdom, hc⟩
Nat.sInf_le- If a natural number $m$ belongs to a set of natural numbers $s$, then the infimum $\operatorname{sInf} s$ is at most $m$.
- The proof of domination (lines 6–13) delegates the check to Lean's computational decision procedure (`decide`), which verifies the dominating property by exhaustive enumeration over all $\binom{4}{3} = 4$ vertices of the 3-token graph rather than through an explicit symbolic argument.
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 of the star graph S_3 is at most 1. -/theorem three_token_star_domination_number_three_le : simple_graph_domination_number (token_graph (SimpleGraph.starGraph (none : Option (Fin 3))) 3) ≤ 1 := by let v1 : { s : Finset (Option (Fin 3)) // s.card = 3 } := ⟨{some 0, some 1, some 2}, by decide⟩ let S : Finset { s : Finset (Option (Fin 3)) // s.card = 3 } := {v1} have hdom : simple_graph_is_dominating (token_graph (SimpleGraph.starGraph (none : Option (Fin 3))) 3) (S : Set _) := by intro v dsimp only [S, v1] unfold token_graph SimpleGraph.starGraph dsimp only revert v decide have hc : S.card = 1 := by decide exact Nat.sInf_le ⟨S, hdom, hc⟩