two_token_domination_number_even_matching_le
Let 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 F_2(G) is at most Fintype.card V / 2.
Statement
open scoped Classical in theorem two_token_domination_number_even_matching_le {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (hreg : Gᶜ.IsRegularOfDegree 1) : simple_graph_domination_number (token_graph G 2) ≤ Fintype.card V / 2
- Formalizes
- arXiv:2611.15124, Theorem 1.3
- Verified
- 14 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
- two_token_domination_number_boundLet 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)…
Read back from the Lean
For any finite type V with decidable equality and any simple graph G on V, if the complement graph Gᶜ is 1-regular (i.e., every vertex has degree 1 in Gᶜ), then the domination number of the 2-token graph of G is at most Fintype.card V / 2 (using natural number division).
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 constructs an explicit dominating set D in the 2-token graph F₂(G) using the 1-factor structure of the complement graph Gᶜ. Because Gᶜ is 1-regular, each vertex v has a unique complement-neighbor p(v), giving a fixed-point-free involution that partitions V into |V|/2 disjoint pairs. Taking D to be the collection of these pairs {v, p(v)} yields a subset of size |V|/2. Any other pair {a, b} not in D has b ≠ p(a), and the non-adjacency of b and p(a) in Gᶜ forces an edge between them in G, making {a, b} adjacent in F₂(G) to the pair {a, p(a)} ∈ D; thus D dominates the graph.
Every vertex v in V has a unique neighbor in the complement graph Gᶜ.
Because Gᶜ is 1-regular by assumption, the degree of each vertex v in Gᶜ is 1. The degree equals the cardinality of the neighbor finset (by SimpleGraph.card_neighborFinset_eq_degree), so the neighbor finset has size 1 and is therefore a singleton {w} (by Finset.card_eq_one.mp). By SimpleGraph.mem_neighborFinset, w is adjacent to v in Gᶜ, and any complement-neighbor y must lie in {w} and hence equal w.
uses
SimpleGraph.card_neighborFinset_eq_degree,Finset.card_eq_one.mp,SimpleGraph.mem_neighborFinsetclassical -- The complement is 1-regular, so every vertex has a unique complement-neighbour. have hex : ∀ v : V, ∃! w, Gᶜ.Adj v w := by intro v have hdeg : (Gᶜ).degree v = 1 := hreg v rw [← SimpleGraph.card_neighborFinset_eq_degree] at hdeg obtain ⟨w, hw⟩ := Finset.card_eq_one.mp hdeg refine ⟨w, ?_, ?_⟩ · have : w ∈ Gᶜ.neighborFinset v := by rw [hw]; simp exact (SimpleGraph.mem_neighborFinset _ _ _).mp this · intro y hy have : y ∈ Gᶜ.neighborFinset v := (SimpleGraph.mem_neighborFinset _ _ _).mpr hy rw [hw] at this simpa using this
There is a fixed-point-free involution p : V → V sending each vertex to its unique complement-neighbor.
Using classical choice (Classical.choose and Classical.choose_spec), let p(v) be the unique complement-neighbor of v. Because simple graphs are loopless, p(v) ≠ v. Since adjacency in Gᶜ is symmetric, v is a complement-neighbor of p(v), so by uniqueness of complement-neighbors, p(p(v)) = v.
uses
Classical.choose,Classical.choose_speclet p : V → V := fun v => Classical.choose (hex v) have hp_adj : ∀ v, Gᶜ.Adj v (p v) := fun v => (Classical.choose_spec (hex v)).1 have hp_uniq : ∀ v w, Gᶜ.Adj v w → w = p v := fun v w h => (Classical.choose_spec (hex v)).2 w h have hp_ne : ∀ v, p v ≠ v := by intro v h exact (Gᶜ).ne_of_adj (hp_adj v) h.symm have hp_invol : ∀ v, p (p v) = v := by intro v exact (hp_uniq (p v) v (hp_adj v).symm).symm
The map f(v) = {v, p v} produces 2-element subsets, and the fiber over f(v) is precisely {v, p v}.
Because p(v) ≠ v, the pair {v, p(v)} has cardinality 2 (by Finset.card_pair), defining a map f from V to the vertex set of the 2-token graph. If f(u) = f(v), then u ∈ f(u) = f(v) = {v, p(v)} (unfolded via Finset.mem_filter, Finset.mem_univ, true_and), forcing u = v or u = p(v) (by Finset.mem_insert, Finset.mem_singleton). Conversely, f(p(v)) = {p(v), p(p(v))} = {p(v), v} = {v, p(v)} = f(v) by the involution property and symmetry of pairs (Finset.pair_comm, Subtype.ext).
uses
Finset.card_pair,Finset.mem_filter,Finset.mem_univ,true_and,Finset.mem_insert,Finset.mem_singleton,Subtype.ext,Finset.pair_comm-- The pairing as a map on 2-element subsets. let f : V → {s : Finset V // s.card = 2} := fun v => ⟨{v, p v}, Finset.card_pair (hp_ne v).symm⟩ have hfib : ∀ v, (Finset.univ.filter (fun u => f u = f v)) = ({v, p v} : Finset V) := by intro v ext u simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_insert, Finset.mem_singleton] constructor · intro h have hmem : u ∈ (f u).val := by simp [f] rw [h] at hmem simpa [f] using hmem · rintro (rfl | rfl) · rfl · apply Subtype.ext change ({p v, p (p v)} : Finset V) = {v, p v} rw [hp_invol, Finset.pair_comm]
The image D = f(V) has cardinality |V| / 2.
The set D is defined as the image of V under f (using Finset.mem_image.mpr, Finset.mem_univ). By fiberwise summation (Finset.card_eq_sum_card_fiberwise, Finset.card_univ), the size of V is the sum of the fiber cardinalities over b ∈ D. Every b ∈ D is of the form f(v) (by Finset.mem_image.mp), whose fiber is {v, p(v)} of size 2 (by Finset.card_pair). Summing 2 over D gives |V| = 2 * |D| (via Finset.sum_congr and Finset.sum_const), and dividing by 2 yields |D| = |V| / 2 (by Nat.mul_div_cancel).
uses
Finset.mem_image.mpr,Finset.mem_univ,Finset.card_eq_sum_card_fiberwise,Finset.card_univ,Finset.mem_image.mp,Finset.card_pair,Finset.sum_congr,Finset.sum_const,Nat.mul_div_cancellet D : Finset {s : Finset V // s.card = 2} := Finset.univ.image f -- `D` has exactly half as many elements as `V`. have hcard : D.card = Fintype.card V / 2 := by have hmaps : Set.MapsTo f (↑(Finset.univ : Finset V)) (↑D) := by intro x hx exact Finset.mem_image.mpr ⟨x, Finset.mem_univ x, rfl⟩ have hsum := Finset.card_eq_sum_card_fiberwise hmaps rw [Finset.card_univ] at hsum have hfiber2 : ∀ b ∈ D, (Finset.univ.filter (fun a => f a = b)).card = 2 := by intro b hb obtain ⟨v, hv, rfl⟩ := Finset.mem_image.mp hb rw [hfib v, Finset.card_pair (hp_ne v).symm] have h1 : Fintype.card V = D.card * 2 := by rw [hsum, Finset.sum_congr rfl hfiber2] simp [Finset.sum_const] rw [h1, Nat.mul_div_cancel _ (by norm_num : 0 < 2)]
For distinct vertices a, b with b ≠ p(a), the symmetric difference of {a, p a} and {a, b} is {b, p a}.
By definition of symmetric difference (Finset.mem_symmDiff, Finset.mem_insert, Finset.mem_singleton), an element c belongs to {a, p(a)} ∆ {a, b} if and only if it is in exactly one of the two sets. Checking the cases c = a, c = p(a), c = b, or c distinct from all three reveals that the shared element a cancels out, while b and p(a) each belong to only one of the sets, leaving {b, p(a)}.
uses
Finset.mem_symmDiff,Finset.mem_insert,Finset.mem_singleton-- Symmetric-difference computation used for the domination step. have hpair : ∀ a b : V, a ≠ b → b ≠ p a → symmDiff ({a, p a} : Finset V) {a, b} = {b, p a} := by intro a b hab hbpa have hapa : a ≠ p a := fun h => (hp_ne a) h.symm ext c rw [Finset.mem_symmDiff] simp only [Finset.mem_insert, Finset.mem_singleton] by_cases hca : c = a · rw [hca]; simp [hapa, hapa.symm, hab, hab.symm, hbpa, hbpa.symm] · by_cases hcp : c = p a · rw [hcp]; simp [hapa, hapa.symm, hab, hab.symm, hbpa, hbpa.symm] · by_cases hcb : c = b · rw [hcb]; simp [hapa, hapa.symm, hab, hab.symm, hbpa, hbpa.symm] · simp [hca, hcp, hcb]
D is a dominating set of the 2-token graph F₂(G).
Let s be a vertex of F₂(G), so s = {a, b} with a ≠ b (by Finset.card_eq_two.mp). If a and b are adjacent in Gᶜ, then b = p(a) by uniqueness, so s = {a, p(a)} = f(a) ∈ D (Finset.mem_image.mpr, Finset.mem_univ, Subtype.ext). If a and b are not complement-adjacent, then b ≠ p(a). Furthermore, b must be adjacent to p(a) in G; otherwise they would be adjacent in Gᶜ, forcing b = p(p(a)) = a, a contradiction. Since {a, p(a)} ∆ {a, b} = {b, p(a)} is an edge of G, s is adjacent to f(a) ∈ D in the 2-token graph.
uses
Finset.card_eq_two.mp,Finset.mem_image.mpr,Finset.mem_univ,Subtype.ext-- `D` is a dominating set of the 2-token graph. have hdom : simple_graph_is_dominating (token_graph G 2) (D : Set {s : Finset V // s.card = 2}) := by intro s obtain ⟨S, hS⟩ := s obtain ⟨a, b, hab, rfl⟩ := Finset.card_eq_two.mp hS by_cases h : Gᶜ.Adj a b · left have hpa : p a = b := (hp_uniq a b h).symm refine Finset.mem_image.mpr ⟨a, Finset.mem_univ a, ?_⟩ apply Subtype.ext change ({a, p a} : Finset V) = {a, b} rw [hpa] · right have hbpa : b ≠ p a := by intro hb exact h (by rw [hb]; exact hp_adj a) have hgadj : G.Adj b (p a) := by by_contra hg have hc : Gᶜ.Adj b (p a) := ⟨hbpa, hg⟩ have hba : b = a := by rw [hp_uniq (p a) b hc.symm, hp_invol] exact hab hba.symm exact ⟨f a, Finset.mem_image.mpr ⟨a, Finset.mem_univ a, rfl⟩, b, p a, hgadj, hpair a b hab hbpa⟩
The domination number of F₂(G) is at most |V| / 2.
The domination number is defined as the infimum of the cardinalities of all dominating sets of the token graph. Since D is a dominating set of size |V| / 2, this infimum is at most |D| = |V| / 2 (by Nat.sInf_le).
uses
Nat.sInf_leunfold simple_graph_domination_number rw [← hcard] exact Nat.sInf_le ⟨D, hdom, rfl⟩
SimpleGraph.card_neighborFinset_eq_degree- The degree of a vertex in a simple graph equals the cardinality of its neighbor finset.
Finset.card_eq_one.mp- A finset has cardinality 1 if and only if it is a singleton {a}.
SimpleGraph.mem_neighborFinset- A vertex belongs to the neighbor finset of v if and only if it is adjacent to v in the graph.
Classical.choose- Given an existence proof, selects a witness element satisfying the predicate.
Classical.choose_spec- The witness chosen by Classical.choose satisfies the given predicate.
Finset.card_pair- The pair set {a, b} has cardinality 2 if and only if a ≠ b.
Finset.mem_filter- An element belongs to a filtered finset if and only if it belongs to the finset and satisfies the predicate.
Finset.mem_univ- Every element of a finite type belongs to the universal finset univ.
true_and- The conjunction of True with any proposition p simplifies to p.
Finset.mem_insert- An element belongs to insert b s if and only if it equals b or belongs to s.
Finset.mem_singleton- An element belongs to the singleton {a} if and only if it equals a.
Subtype.ext- Two subtype elements are equal if their underlying values are equal.
Finset.pair_comm- The unordered pair {a, b} equals {b, a}.
Finset.mem_image.mpr- An element is in the image finset f(s) if it is the image of some element in s.
Finset.card_eq_sum_card_fiberwise- The cardinality of a finset s equals the sum of the cardinalities of its fibers under a map f.
Finset.card_univ- The cardinality of the universal finset is the cardinality of the underlying finite type.
Finset.mem_image.mp- If an element is in the image finset f(s), then it is the image of some element in s.
Finset.sum_congr- Two sums over equal finsets are equal if their summands agree on every element.
Finset.sum_const- The sum of a constant value over a finset equals the cardinality of the finset multiplied by the constant.
Nat.mul_div_cancel- Multiplying a natural number by a positive integer n and then dividing by n gives back the original number.
Finset.mem_symmDiff- An element belongs to the symmetric difference s ∆ t if and only if it belongs to exactly one of s or t.
Finset.card_eq_two.mp- A finset has cardinality 2 if and only if it is of the form {x, y} with x ≠ y.
Nat.sInf_le- The infimum of a set of natural numbers is at most any member of the set.
- The vertices of the 2-token graph are formally represented as subtypes `{s : Finset V // s.card = 2}`. Elements of D and edges between pairs carry proof terms of cardinality 2 that are eliminated by `Subtype.ext` (extensionality of subtypes).
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/-- If the complement of G is 1-regular (a 1-factor), then the domination number of F_2(G) is at most n / 2. -/theorem two_token_domination_number_even_matching_le {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (hreg : Gᶜ.IsRegularOfDegree 1) : simple_graph_domination_number (token_graph G 2) ≤ Fintype.card V / 2 := by classical -- The complement is 1-regular, so every vertex has a unique complement-neighbour. have hex : ∀ v : V, ∃! w, Gᶜ.Adj v w := by intro v have hdeg : (Gᶜ).degree v = 1 := hreg v rw [← SimpleGraph.card_neighborFinset_eq_degree] at hdeg obtain ⟨w, hw⟩ := Finset.card_eq_one.mp hdeg refine ⟨w, ?_, ?_⟩ · have : w ∈ Gᶜ.neighborFinset v := by rw [hw]; simp exact (SimpleGraph.mem_neighborFinset _ _ _).mp this · intro y hy have : y ∈ Gᶜ.neighborFinset v := (SimpleGraph.mem_neighborFinset _ _ _).mpr hy rw [hw] at this simpa using this let p : V → V := fun v => Classical.choose (hex v) have hp_adj : ∀ v, Gᶜ.Adj v (p v) := fun v => (Classical.choose_spec (hex v)).1 have hp_uniq : ∀ v w, Gᶜ.Adj v w → w = p v := fun v w h => (Classical.choose_spec (hex v)).2 w h have hp_ne : ∀ v, p v ≠ v := by intro v h exact (Gᶜ).ne_of_adj (hp_adj v) h.symm have hp_invol : ∀ v, p (p v) = v := by intro v exact (hp_uniq (p v) v (hp_adj v).symm).symm -- The pairing as a map on 2-element subsets. let f : V → {s : Finset V // s.card = 2} := fun v => ⟨{v, p v}, Finset.card_pair (hp_ne v).symm⟩ have hfib : ∀ v, (Finset.univ.filter (fun u => f u = f v)) = ({v, p v} : Finset V) := by intro v ext u simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_insert, Finset.mem_singleton] constructor · intro h have hmem : u ∈ (f u).val := by simp [f] rw [h] at hmem simpa [f] using hmem · rintro (rfl | rfl) · rfl · apply Subtype.ext change ({p v, p (p v)} : Finset V) = {v, p v} rw [hp_invol, Finset.pair_comm] let D : Finset {s : Finset V // s.card = 2} := Finset.univ.image f -- `D` has exactly half as many elements as `V`. have hcard : D.card = Fintype.card V / 2 := by have hmaps : Set.MapsTo f (↑(Finset.univ : Finset V)) (↑D) := by intro x hx exact Finset.mem_image.mpr ⟨x, Finset.mem_univ x, rfl⟩ have hsum := Finset.card_eq_sum_card_fiberwise hmaps rw [Finset.card_univ] at hsum have hfiber2 : ∀ b ∈ D, (Finset.univ.filter (fun a => f a = b)).card = 2 := by intro b hb obtain ⟨v, hv, rfl⟩ := Finset.mem_image.mp hb rw [hfib v, Finset.card_pair (hp_ne v).symm] have h1 : Fintype.card V = D.card * 2 := by rw [hsum, Finset.sum_congr rfl hfiber2] simp [Finset.sum_const] rw [h1, Nat.mul_div_cancel _ (by norm_num : 0 < 2)] -- Symmetric-difference computation used for the domination step. have hpair : ∀ a b : V, a ≠ b → b ≠ p a → symmDiff ({a, p a} : Finset V) {a, b} = {b, p a} := by intro a b hab hbpa have hapa : a ≠ p a := fun h => (hp_ne a) h.symm ext c rw [Finset.mem_symmDiff] simp only [Finset.mem_insert, Finset.mem_singleton] by_cases hca : c = a · rw [hca]; simp [hapa, hapa.symm, hab, hab.symm, hbpa, hbpa.symm] · by_cases hcp : c = p a · rw [hcp]; simp [hapa, hapa.symm, hab, hab.symm, hbpa, hbpa.symm] · by_cases hcb : c = b · rw [hcb]; simp [hapa, hapa.symm, hab, hab.symm, hbpa, hbpa.symm] · simp [hca, hcp, hcb] -- `D` is a dominating set of the 2-token graph. have hdom : simple_graph_is_dominating (token_graph G 2) (D : Set {s : Finset V // s.card = 2}) := by intro s obtain ⟨S, hS⟩ := s obtain ⟨a, b, hab, rfl⟩ := Finset.card_eq_two.mp hS by_cases h : Gᶜ.Adj a b · left have hpa : p a = b := (hp_uniq a b h).symm refine Finset.mem_image.mpr ⟨a, Finset.mem_univ a, ?_⟩ apply Subtype.ext change ({a, p a} : Finset V) = {a, b} rw [hpa] · right have hbpa : b ≠ p a := by intro hb exact h (by rw [hb]; exact hp_adj a) have hgadj : G.Adj b (p a) := by by_contra hg have hc : Gᶜ.Adj b (p a) := ⟨hbpa, hg⟩ have hba : b = a := by rw [hp_uniq (p a) b hc.symm, hp_invol] exact hab hba.symm exact ⟨f a, Finset.mem_image.mpr ⟨a, Finset.mem_univ a, rfl⟩, b, p a, hgadj, hpair a b hab hbpa⟩ unfold simple_graph_domination_number rw [← hcard] exact Nat.sInf_le ⟨D, hdom, rfl⟩