AFTD Auto-Formalizing Theoretical Domains

three_token_k2n_domination_number_four_le

theoremverified

The domination number of the 3-token graph F_3(K_{2,4}) of the complete bipartite graph K_{2,4} is at most 4.

Statement

theorem three_token_k2n_domination_number_four_le :
    simple_graph_domination_number (token_graph (completeBipartiteGraph (Fin 2) (Fin 4)) 3) ≤ 4
Source
step towards three_token_k2n_domination_number_four
Verified
01 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • simple_graph_domination_numberThe domination number gamma(G) of a finite simple graph G is the minimum cardinality of a dominating set of G.
  • 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.
Used by 1

The proof, explained

The proof explicitly constructs a dominating set $S = \{v_1, v_2, v_3, v_4\}$ of size 4 in the 3-token graph $F_3(K_{2,4})$. Since the graph has only $\binom{6}{3} = 20$ vertices, Lean verifies by exhaustive computation that every vertex is in $S$ or adjacent to a vertex in $S$. The result then follows from the definition of the domination number as the infimum of the sizes of dominating sets.

  1. Define a candidate dominating set $S = \\{v_1, v_2, v_3, v_4\\}$ consisting of four vertices in the token graph.

    Vertices of the 3-token graph $F_3(K_{2,4})$ are 3-element subsets of the 6-element vertex set $\\mathrm{Fin}\\,2 \\oplus \\mathrm{Fin}\\,4$. We define four explicit 3-element subsets $v_1, v_2, v_3, v_4$ (each verified to have cardinality 3 by Lean's `decide` tactic) and gather them into the subset $S = \\{v_1, v_2, v_3, v_4\\}$.

    lines 4–8

      let v1 : { s : Finset (Fin 2 ⊕ Fin 4) // s.card = 3 } := ⟨{Sum.inl 0, Sum.inl 1, Sum.inr 1}, by decide⟩
      let v2 : { s : Finset (Fin 2 ⊕ Fin 4) // s.card = 3 } := ⟨{Sum.inl 0, Sum.inr 1, Sum.inr 2}, by decide⟩
      let v3 : { s : Finset (Fin 2 ⊕ Fin 4) // s.card = 3 } := ⟨{Sum.inl 1, Sum.inr 0, Sum.inr 3}, by decide⟩
      let v4 : { s : Finset (Fin 2 ⊕ Fin 4) // s.card = 3 } := ⟨{Sum.inr 0, Sum.inr 2, Sum.inr 3}, by decide⟩
      let S : Finset { s : Finset (Fin 2 ⊕ Fin 4) // s.card = 3 } := {v1, v2, v3, v4}
  2. The set $S$ is a dominating set in $F_3(K_{2,4})$. automation

    By definition, $S$ dominates if every vertex $v$ of the token graph is either in $S$ or adjacent to some vertex in $S$. We introduce a generic vertex $v$, expand the definitions of $S$, each $v_i$, the token graph adjacency relation, and the complete bipartite graph $K_{2,4}$, and revert $v$. This produces a universally quantified proposition over the finite vertex set (of size $\\binom{6}{3} = 20$), which Lean verifies exhaustively using `decide`.

    lines 9–15

      have hdom : simple_graph_is_dominating (token_graph (completeBipartiteGraph (Fin 2) (Fin 4)) 3) (S : Set _) := by
        intro v
        dsimp only [S, v1, v2, v3, v4]
        unfold token_graph completeBipartiteGraph
        dsimp only
        revert v
        decide
  3. The set $S$ has cardinality 4. automation

    Because the four vertices $v_1, v_2, v_3, v_4$ are pairwise distinct, the set $S$ has exactly 4 elements; this is verified by direct computation with `decide`.

    line 16

      have hc : S.card = 4 := by decide
  4. The domination number of $F_3(K_{2,4})$ is at most 4.

    The domination number of a graph is defined as the infimum of the cardinalities of all its dominating sets. Because $S$ is a dominating set of size 4, the number 4 belongs to this set of cardinalities, so `Nat.sInf_le` yields that the domination number is at most 4.

    line 17

    uses Nat.sInf_le

      exact Nat.sInf_le ⟨S, hdom, hc⟩
Nat.sInf_le
For any set $s \\subseteq \\mathbb{N}$ and any element $m \\in s$, 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 F_3(K_{2,4}) is at most 4. -/theorem three_token_k2n_domination_number_four_le :    simple_graph_domination_number (token_graph (completeBipartiteGraph (Fin 2) (Fin 4)) 3) ≤ 4 := by  let v1 : { s : Finset (Fin 2 ⊕ Fin 4) // s.card = 3 } := ⟨{Sum.inl 0, Sum.inl 1, Sum.inr 1}, by decide⟩  let v2 : { s : Finset (Fin 2 ⊕ Fin 4) // s.card = 3 } := ⟨{Sum.inl 0, Sum.inr 1, Sum.inr 2}, by decide⟩  let v3 : { s : Finset (Fin 2 ⊕ Fin 4) // s.card = 3 } := ⟨{Sum.inl 1, Sum.inr 0, Sum.inr 3}, by decide⟩  let v4 : { s : Finset (Fin 2 ⊕ Fin 4) // s.card = 3 } := ⟨{Sum.inr 0, Sum.inr 2, Sum.inr 3}, by decide⟩  let S : Finset { s : Finset (Fin 2 ⊕ Fin 4) // s.card = 3 } := {v1, v2, v3, v4}  have hdom : simple_graph_is_dominating (token_graph (completeBipartiteGraph (Fin 2) (Fin 4)) 3) (S : Set _) := by    intro v    dsimp only [S, v1, v2, v3, v4]    unfold token_graph completeBipartiteGraph    dsimp only    revert v    decide  have hc : S.card = 4 := by decide  exact Nat.sInf_le ⟨S, hdom, hc⟩
See it in the graphDiscuss this resultChallenge it