three_token_star_domination_number_three
The domination number of the 3-token graph of the star graph SimpleGraph.starGraph (none : Option (Fin 3)) is 1.
Statement
theorem three_token_star_domination_number_three :
simple_graph_domination_number (token_graph (SimpleGraph.starGraph (none : Option (Fin 3))) 3) = 1- Formalizes
- arXiv:2611.11191, Subsection 4.4
- Verified
- 11 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_star_domination_number_three_leThe domination number of the 3-token graph of the star graph SimpleGraph.starGraph (none : Option (Fin 3)) is at most 1.
- 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.
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 equal to 1.
More explicitly:
- The base graph is SimpleGraph.starGraph (none : Option (Fin 3)), which is the star graph with vertex set Option (Fin 3) (having 4 vertices: none and some i for i ∈ Fin 3), with center none and edges between none and each leaf some i.
- The 3-token graph has as vertices the 3-element subsets of Option (Fin 3) (i.e., { s : Finset (Option (Fin 3)) // s.card = 3 }), where two subsets are adjacent if and only if their symmetric difference is a 2-element set {u, v} such that u and v are adjacent in the star graph.
- The domination number is the minimum cardinality of a dominating set of vertices in this 3-token graph (a set S of vertices such that every vertex is either in S or adjacent to a vertex in S).
- The theorem states that this domination number is 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 proof establishes that the domination number is 1 by combining the known upper bound γ ≤ 1 with the lower bound γ ≥ 1. The lower bound follows because the domination number is the minimum cardinality of a dominating set, and any dominating set must be non-empty since the empty set cannot dominate any vertex.
To show that the domination number is 1, it suffices to prove that the infimum of cardinalities of all dominating sets is at least 1.
By antisymmetry of the order (`le_antisymm`), combining the lower bound with the previously established upper bound (`three_token_star_domination_number_three_le`) yields equality. Unfolding the definition of the domination number expresses it as the infimum of sizes of dominating sets in the 3-token graph, whose vertices V are the 3-element subsets of Option (Fin 3).
uses
le_antisymm,three_token_star_domination_number_three_leapply le_antisymm three_token_star_domination_number_three_le unfold simple_graph_domination_number set V := { s : Finset (Option (Fin 3)) // s.card = 3 }
The set of cardinalities of dominating sets is non-empty. automation
We introduce a candidate vertex v₁ = {some 0, some 1, some 2} in V and let S = {v₁}. Since the 4-vertex star graph S₃ has only 4 possible 3-element configurations, finite computation (`decide`) exhaustively verifies that every configuration is either v₁ or adjacent to v₁. Thus S is a dominating set of cardinality 1, making the set of dominating set sizes non-empty.
have hne : {k : ℕ | ∃ S : Finset V, simple_graph_is_dominating (token_graph (SimpleGraph.starGraph none) 3) (↑S : Set V) ∧ S.card = k}.Nonempty := by let v1 : V := ⟨{some 0, some 1, some 2}, by decide⟩ let S : Finset V := {v1} have hdom : simple_graph_is_dominating (token_graph (SimpleGraph.starGraph none) 3) (↑S : Set V) := by intro v dsimp only [S, v1] unfold token_graph SimpleGraph.starGraph dsimp only revert v decide exact ⟨1, S, hdom, by decide⟩
There exists a dominating set S whose cardinality equals the domination number, reducing the goal to 1 ≤ |S|.
Because the set of sizes of dominating sets is a non-empty set of natural numbers, its infimum is attained by an actual element of the set (`Nat.sInf_mem`). We unpack this witness to obtain a dominating set S with |S| equal to the infimum, and rewrite the goal as 1 ≤ |S|.
uses
Nat.sInf_memhave hmem := Nat.sInf_mem hne dsimp at hmem rcases hmem with ⟨S, hdom, hcard⟩ rw [← hcard]
If |S| < 1, then S must be the empty set.
We argue by contradiction and assume ¬(1 ≤ |S|). For natural numbers, this implies |S| = 0 (by linear integer arithmetic `omega`). By `Finset.card_eq_zero.mp`, a finite set with cardinality 0 is empty, so S = ∅.
uses
Finset.card_eq_zero.mpby_contra h0 have hS_empty : S = ∅ := by apply Finset.card_eq_zero.mp omega
The empty set cannot dominate any vertex, producing a contradiction.
We consider the vertex v₀ = {some 0, some 1, some 2} in V. Since S is dominating, v₀ must be in S or adjacent to an element of S. Substituting S = ∅ makes both alternatives false, completing the contradiction.
let v0 : V := ⟨{some 0, some 1, some 2}, by decide⟩ have hv := hdom v0 rw [hS_empty] at hv simp at hv
le_antisymm- In a partial order, if a ≤ b and b ≤ a, then a = b.
three_token_star_domination_number_three_le- The domination number of the 3-token graph of the star graph on Option (Fin 3) is at most 1.
Nat.sInf_mem- Any non-empty set of natural numbers contains its infimum (minimum).
Finset.card_eq_zero.mp- A finite set whose cardinality is 0 is the empty set.
- The proof that the singleton {v₁} is a dominating set is verified by exhaustive computation (`decide`) over all four 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 of the star graph S_3 is 1. -/theorem three_token_star_domination_number_three : simple_graph_domination_number (token_graph (SimpleGraph.starGraph (none : Option (Fin 3))) 3) = 1 := by apply le_antisymm three_token_star_domination_number_three_le unfold simple_graph_domination_number set V := { s : Finset (Option (Fin 3)) // s.card = 3 } have hne : {k : ℕ | ∃ S : Finset V, simple_graph_is_dominating (token_graph (SimpleGraph.starGraph none) 3) (↑S : Set V) ∧ S.card = k}.Nonempty := by let v1 : V := ⟨{some 0, some 1, some 2}, by decide⟩ let S : Finset V := {v1} have hdom : simple_graph_is_dominating (token_graph (SimpleGraph.starGraph none) 3) (↑S : Set V) := by intro v dsimp only [S, v1] unfold token_graph SimpleGraph.starGraph dsimp only revert v decide exact ⟨1, S, hdom, by decide⟩ have hmem := Nat.sInf_mem hne dsimp at hmem rcases hmem with ⟨S, hdom, hcard⟩ rw [← hcard] by_contra h0 have hS_empty : S = ∅ := by apply Finset.card_eq_zero.mp omega let v0 : V := ⟨{some 0, some 1, some 2}, by decide⟩ have hv := hdom v0 rw [hS_empty] at hv simp at hv