AFTD Auto-Formalizing Theoretical Domains

three_token_star_domination_number_four

theoremverifiedformalization

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.

  1. 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.

    lines 1–14

    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}
    
  2. 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.

    lines 15–27

    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
  3. 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`.

    lines 28–30

    uses Nat.sInf_le

      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⟩
    
  4. 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.

    lines 31–38

    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
    
  5. 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`.

    lines 39–48

    uses Finset.mem_univ

    theorem 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
  6. 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.

    lines 49–56

    uses Nat.sInf_mem, Nat.le_of_lt_succ, not_le.mp, three_token_star_domination_number_four_no_dom_two

      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
    
  7. 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.

    lines 57–59

    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.

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

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
See it in the graphDiscuss this resultChallenge it