two_token_domination_number_bound
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
- two_token_domination_number_ge_ceil_halfLet 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)…
- two_token_domination_number_even_matching_leLet G be a finite simple graph on vertex type V whose complement graph Gᶜ is 1-regular. Then the domination number of the 2-token graph…
- two_token_domination_number_odd_p3_matching_leLet G be a finite simple graph on vertex type V whose complement graph Gᶜ has a unique vertex of degree 2 and all other vertices of degree…
- 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…
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.
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.
uses
two_token_domination_number_ge_ceil_halfhave h_ge := two_token_domination_number_ge_ceil_half G hγ refine ⟨h_ge, fun h_or => ?_⟩
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.
rcases h_or with h1 | h2
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.
uses
two_token_domination_number_even_matching_le· have h_le := two_token_domination_number_even_matching_le G h1 omega
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`).
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.
- In the 1-regular case, the formal proof does not need to use the graph-theoretic fact that a 1-regular graph has an even number of vertices. The integer division inequalities $(|V| + 1) / 2 \le X \le |V| / 2$ already algebraically force $|V|$ to be even and $X = (|V| + 1) / 2$, which `omega` resolves automatically.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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