AFTD Auto-Formalizing Theoretical Domains

three_token_star_domination_number_three

theoremverifiedformalization

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.

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

    lines 4–6

    uses le_antisymm, three_token_star_domination_number_three_le

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

    lines 7–18

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

    lines 19–22

    uses Nat.sInf_mem

      have hmem := Nat.sInf_mem hne
      dsimp at hmem
      rcases hmem with ⟨S, hdom, hcard⟩
      rw [← hcard]
  4. 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 = ∅.

    lines 23–26

    uses Finset.card_eq_zero.mp

      by_contra h0
      have hS_empty : S = ∅ := by
        apply Finset.card_eq_zero.mp
        omega
  5. 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.

    lines 27–30

      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.

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