AFTD Auto-Formalizing Theoretical Domains

three_token_star_domination_number_three_le

theoremverified

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

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.

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

    lines 4–5

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

    lines 6–13

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

    line 14

      have hc : S.card = 1 := by decide
  4. 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.

    line 15

    uses Nat.sInf_le

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

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

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