AFTD Auto-Formalizing Theoretical Domains

two_token_domination_number_bound

theoremverifiedformalization

Let G be a finite simple graph on vertex type V with domination number at least 2. Then the domination number of the 2-token graph F_2(G) is at least (Fintype.card V + 1) / 2. Furthermore, if the complement graph Gᶜ is 1-regular, or has a vertex of degree 2 with all other vertices having degree 1, then the domination number of F_2(G) equals (Fintype.card V + 1) / 2.

Statement

open scoped Classical in
theorem two_token_domination_number_bound {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) (hγ : 2 ≤ simple_graph_domination_number G) :
    (Fintype.card V + 1) / 2 ≤ simple_graph_domination_number (token_graph G 2) ∧
    ((Gᶜ.IsRegularOfDegree 1 ∨
      ∃ v : V, Gᶜ.degree v = 2 ∧ ∀ u : V, u ≠ v → Gᶜ.degree u = 1) →
     simple_graph_domination_number (token_graph G 2) = (Fintype.card V + 1) / 2)
Formalizes
arXiv:2611.15124, Theorem 1.3
Verified
14 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5

Read back from the Lean

Let $V$ be a finite type with decidable equality, and let $G$ be a simple graph on $V$. Assume that the domination number of $G$ is at least 2 (i.e., every dominating set in $G$ has size at least 2). Then the following two statements hold: 1. The domination number of the 2-token graph of $G$ is at least $(|V| + 1) / 2$ (under natural number division, i.e., $\lceil |V| / 2 \rceil$). 2. If the complement graph $G^c$ is 1-regular, or if there exists a vertex $v \in V$ such that the degree of $v$ in $G^c$ is 2 and all vertices $u \neq v$ have degree 1 in $G^c$, then the domination number of the 2-token graph of $G$ equals $(|V| + 1) / 2$.

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 theorem establishes both a general lower bound on the domination number of the 2-token graph F_2(G) and an exact formula for graphs whose complements have specific regular or near-regular structures. The lower bound (|V| + 1) / 2 ≤ γ(F_2(G)) is supplied directly by an existing lemma for graphs with domination number at least 2. To prove equality under the given complement conditions, the proof splits into two cases and invokes corresponding upper bound lemmas (giving at most |V| / 2 for 1-regular complements, and at most (|V| + 1) / 2 for P_3-plus-matching complements), closing each case with linear integer arithmetic.

  1. The domination number of F_2(G) is at least (|V| + 1) / 2, and it suffices to prove equality under the assumption that Gᶜ is 1-regular or has one vertex of degree 2 with all other vertices of degree 1.

    We apply `two_token_domination_number_ge_ceil_half` to the hypothesis γ(G) ≥ 2 to obtain the lower bound (|V| + 1) / 2 ≤ γ(F_2(G)). We provide this as the first conjunct and assume the disjunctive premise for the second conjunct.

    lines 9–10

    uses two_token_domination_number_ge_ceil_half

      have h_ge := two_token_domination_number_ge_ceil_half G hγ
      refine ⟨h_ge, fun h_or => ?_⟩
  2. It suffices to establish γ(F_2(G)) = (|V| + 1) / 2 in each of the two cases given by the hypothesis.

    We perform a case split (`rcases`) on the assumption that either Gᶜ is 1-regular or Gᶜ has a unique vertex of degree 2 with all other vertices of degree 1.

    line 11

      rcases h_or with h1 | h2
  3. If Gᶜ is 1-regular, then γ(F_2(G)) = (|V| + 1) / 2.

    By `two_token_domination_number_even_matching_le`, we have γ(F_2(G)) ≤ |V| / 2. Combining this with the lower bound (|V| + 1) / 2 ≤ γ(F_2(G)), linear integer arithmetic (`omega`) deduces that |V| must be even and γ(F_2(G)) = (|V| + 1) / 2.

    lines 12–13

    uses two_token_domination_number_even_matching_le

      · have h_le := two_token_domination_number_even_matching_le G h1
        omega
  4. If Gᶜ has a vertex of degree 2 and all other vertices have degree 1, then γ(F_2(G)) = (|V| + 1) / 2.

    By `two_token_domination_number_odd_p3_matching_le`, we have γ(F_2(G)) ≤ (|V| + 1) / 2. Together with the lower bound (|V| + 1) / 2 ≤ γ(F_2(G)), the equality follows immediately by antisymmetry via linear integer arithmetic (`omega`).

    lines 14–15

    uses two_token_domination_number_odd_p3_matching_le

      · have h_le := two_token_domination_number_odd_p3_matching_le G h2
        omega
two_token_domination_number_ge_ceil_half
If a finite simple graph G has domination number at least 2, then the domination number of its 2-token graph F_2(G) is at least (|V| + 1) / 2.
two_token_domination_number_even_matching_le
If the complement graph Gᶜ is 1-regular, then the domination number of the 2-token graph F_2(G) is at most |V| / 2.
two_token_domination_number_odd_p3_matching_le
If the complement graph Gᶜ has a vertex of degree 2 and all other vertices have degree 1, then the domination number of the 2-token graph F_2(G) is at most (|V| + 1) / 2.

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

open scoped Classical in/-- Lower bound on the domination number of 2-token graphs for graphs without universal vertices, with equality for graphs whose complement is a 1-factor or P_3 union disjoint edges. -/theorem two_token_domination_number_bound {V : Type*} [Fintype V] [DecidableEq V]    (G : SimpleGraph V) (hγ : 2 ≤ simple_graph_domination_number G) :    (Fintype.card V + 1) / 2 ≤ simple_graph_domination_number (token_graph G 2) ∧    ((Gᶜ.IsRegularOfDegree 1 ∨      ∃ v : V, Gᶜ.degree v = 2 ∧ ∀ u : V, u ≠ v → Gᶜ.degree u = 1) →     simple_graph_domination_number (token_graph G 2) = (Fintype.card V + 1) / 2) := by  have h_ge := two_token_domination_number_ge_ceil_half G hγ  refine ⟨h_ge, fun h_or => ?_⟩  rcases h_or with h1 | h2  · have h_le := two_token_domination_number_even_matching_le G h1    omega  · have h_le := two_token_domination_number_odd_p3_matching_le G h2    omega
See it in the graphDiscuss this resultChallenge it