two_token_k2_nminus2_has_dominating_set
For every integer n ≥ 4, there exists a dominating set of the 2-token graph F_2(K_{2,n-2}) of cardinality at most n - 2.
Statement
theorem two_token_k2_nminus2_has_dominating_set (n : ℕ) (hn : 4 ≤ n) :
∃ S : Finset { s : Finset (Fin 2 ⊕ Fin (n - 2)) // s.card = 2 },
simple_graph_is_dominating (token_graph (completeBipartiteGraph (Fin 2) (Fin (n - 2))) 2) (S : Set _) ∧
S.card ≤ n - 2- Source
- arXiv:2611.15124 Proposition 3.1 -- Domination in token graphs of graphs with domination number two
- Verified
- 16 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_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.
- two_token_kmn_ll_vertexThe LL vertex {x,y} determined by two distinct left vertices x != y.
- two_token_kmn_lr_vertexThe LR vertex {x,y} determined by a left vertex x and a right vertex y.
Read back from the Lean
For every natural number $n \ge 4$, there exists a finite set $S$ of 2-element subsets of $\mathrm{Fin}(2) \oplus \mathrm{Fin}(n - 2)$ such that: 1. $S$ (viewed as a set) is a dominating set of the 2-token graph of the complete bipartite graph $K_{2, n-2}$ (with parts $\mathrm{Fin}(2)$ and $\mathrm{Fin}(n - 2)$); and 2. The cardinality of $S$ is at most $n - 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
To construct a dominating set of size at most n - 2 for the 2-token graph F_2(K_{2, n-2}), we fix an element z ∈ Fin(n - 2) and choose S to consist of the unique 2-token on the left part, ll = {0, 1}, together with the n - 3 mixed pairs {0, j} for j ≠ z. This set S has cardinality 1 + (n - 3) = n - 2. Any vertex of F_2(K_{2, n-2}) is either in S or dominated by S: {0, 1} and the pairs {0, j} (j ≠ z) are already in S; {0, z} and all pairs {1, b} are adjacent to ll; and any pair {b1, b2} on the right part is adjacent to {0, b2} (if b1 = z) or {0, b1} (if b1 ≠ z).
Any 2-element subset of A ⊕ B is either two distinct elements of A, a mixed pair from A and B, or two distinct elements of B.
By `Finset.card_eq_two`, a finset s of size 2 is of the form {x, y} with x ≠ y. Case splitting on whether x and y lie in A (via Sum.inl) or B (via Sum.inr) yields the three cases, using `Finset.pair_comm` to reorder the mixed pair when x ∈ B and y ∈ A.
uses
Finset.card_eq_two,Finset.pair_commrw [Finset.card_eq_two] at hs rcases hs with ⟨x, y, hne, rfl⟩ rcases x with a1 | b1 <;> rcases y with a2 | b2 · left refine ⟨a1, a2, ?_, rfl⟩ rintro rfl; exact hne rfl · right; left; exact ⟨a1, b2, rfl⟩ · right; left; refine ⟨a2, b1, ?_⟩; rw [Finset.pair_comm] · right; right refine ⟨b1, b2, ?_, rfl⟩ rintro rfl; exact hne rfl
Any pair of distinct elements in Fin 2 embedded into Fin 2 ⊕ Fin k equals {0, 1}.
Exhaustive case analysis on a1, a2 ∈ Fin 2 using `fin_cases`. The cases where a1 = a2 are impossible by the hypothesis a1 ≠ a2; the case (0, 1) holds by definition; and the case (1, 0) follows by pair commutativity (`Finset.pair_comm`).
uses
Finset.pair_commrevert hne fin_cases a1 <;> fin_cases a2 · intro h; contradiction · intro _; rfl · intro _; rw [Finset.pair_comm]; rfl · intro h; contradiction
Define a candidate dominating set S of vertices consisting of ll = {0, 1} and the mixed pairs {0, j} for all j ≠ z in Fin(n - 2).
Since n ≥ 4, n - 2 > 0 by linear arithmetic (`omega`). We pick z = 0 ∈ Fin(n - 2) as a fixed reference element. We define ll as the unique pair of vertices in Fin 2, and lr_part as the image under j ↦ {0, j} of Fin(n - 2) with z removed. We set S = insert ll lr_part and prepare to show S dominates the graph and has size at most n - 2.
have hk : 0 < n - 2 := by omega let z : Fin (n - 2) := ⟨0, hk⟩ let ll : { s : Finset (Fin 2 ⊕ Fin (n - 2)) // s.card = 2 } := two_token_kmn_ll_vertex (0 : Fin 2) (1 : Fin 2) (by decide) let lr_part := (Finset.univ.erase z).image (fun j => two_token_kmn_lr_vertex (0 : Fin 2) j) let S : Finset { s : Finset (Fin 2 ⊕ Fin (n - 2)) // s.card = 2 } := insert ll lr_part refine ⟨S, ?_, ?_⟩
Every vertex whose two tokens both lie in Fin 2 belongs to S.
We classify an arbitrary vertex v using `two_token_k2_nminus2_has_dominating_set_finset_card_two_cases`. When both tokens lie in Fin 2, lemma `two_token_k2_nminus2_has_dominating_set_fin2_pair_eq` shows that v equals ll as an underlying set, hence v = ll by `Subtype.ext`. Since ll ∈ S by `Finset.mem_insert_self`, v is in S.
uses
two_token_k2_nminus2_has_dominating_set_finset_card_two_cases,two_token_k2_nminus2_has_dominating_set_fin2_pair_eq,Subtype.ext,Finset.mem_insert_self· intro v rcases two_token_k2_nminus2_has_dominating_set_finset_card_two_cases v.val v.property with (⟨a1, a2, hne, hs⟩ | ⟨a, b, hs⟩ | ⟨b1, b2, hne, hs⟩) · -- Case LL left have h_eq : v = ll := by apply Subtype.ext dsimp [ll, two_token_kmn_ll_vertex] rw [hs] exact two_token_k2_nminus2_has_dominating_set_fin2_pair_eq a1 a2 hne rw [h_eq] exact Finset.mem_insert_self _ _ · -- Case LR
The mixed vertex v = {0, z} is adjacent to ll ∈ S. automation
When v = {a, b} with a = 0 and b = z, the symmetric difference of ll = {0, 1} and v = {0, z} is {1, z}. Since 1 ∈ Fin 2 and z ∈ Fin(n - 2), this is an edge of the complete bipartite graph K_{2, n-2}. Therefore ll is adjacent to v in the 2-token graph. The set equality is discharged by `aesop` after simplifying membership conditions.
uses
Finset.mem_insert_self,Finset.mem_symmDiff,Finset.mem_insert,Finset.mem_singletonfin_cases a · -- a = 0 by_cases hb : b = z · -- b = z subst hb right refine ⟨ll, Finset.mem_insert_self _ _, ?_⟩ refine ⟨Sum.inl (1 : Fin 2), Sum.inr z, ?_, ?_⟩ · dsimp [completeBipartiteGraph]; left; simp · ext x simp only [Finset.mem_symmDiff, Finset.mem_insert, Finset.mem_singleton] rw [hs] dsimp [ll, two_token_kmn_ll_vertex] aesop · -- b ≠ zEvery mixed vertex v = {0, b} with b ≠ z belongs to S.
When a = 0 and b ≠ z, v is the vertex {0, b} by `Subtype.ext`. Since b ∈ Fin(n - 2) \ {z}, {0, b} belongs to lr_part by `Finset.mem_image_of_mem`, and hence belongs to S by `Finset.mem_insert_of_mem`.
uses
Subtype.ext,Finset.mem_insert_of_mem,Finset.mem_image_of_memleft have h_eq : v = two_token_kmn_lr_vertex (0 : Fin 2) b := by apply Subtype.ext exact hs rw [h_eq] apply Finset.mem_insert_of_mem dsimp [lr_part] apply Finset.mem_image_of_mem simp [hb] · -- a = 1
Every mixed vertex v = {1, b} is adjacent to ll ∈ S. automation
When a = 1, for any b ∈ Fin(n - 2), the symmetric difference of ll = {0, 1} and v = {1, b} is {0, b}, which connects 0 ∈ Fin 2 and b ∈ Fin(n - 2) and is thus an edge of K_{2, n-2}. Hence ll ∈ S is adjacent to v, verified via `aesop`.
uses
Finset.mem_insert_self,Finset.mem_symmDiff,Finset.mem_insert,Finset.mem_singletonright refine ⟨ll, Finset.mem_insert_self _ _, ?_⟩ refine ⟨Sum.inl (0 : Fin 2), Sum.inr b, ?_, ?_⟩ · dsimp [completeBipartiteGraph]; left; simp · ext x simp only [Finset.mem_symmDiff, Finset.mem_insert, Finset.mem_singleton] rw [hs] dsimp [ll, two_token_kmn_ll_vertex] aesop · -- Case RR
Every vertex v = {b1, b2} whose tokens both lie in Fin(n - 2) is adjacent to a vertex in S. automation
Since b1 ≠ b2, at most one of them can equal z. If b1 = z, then b2 ≠ z, and we pick u = {0, b2} ∈ lr_part ⊆ S; the symmetric difference u Δ v is {0, b1} = {0, z}, an edge of K_{2, n-2}. If b1 ≠ z, we pick u = {0, b1} ∈ lr_part ⊆ S; then u Δ v is {0, b2}, also an edge. In each case `aesop` verifies the symmetric difference.
uses
Finset.mem_insert_of_mem,Finset.mem_image_of_mem,Finset.mem_symmDiff,Finset.mem_insert,Finset.mem_singletonright by_cases hb1 : b1 = z · have hb2 : b2 ≠ z := by intro h; subst h; subst hb1; exact hne rfl let u := two_token_kmn_lr_vertex (0 : Fin 2) b2 have hu : u ∈ S := by apply Finset.mem_insert_of_mem dsimp [lr_part] apply Finset.mem_image_of_mem simp [hb2] refine ⟨u, hu, ?_⟩ refine ⟨Sum.inl (0 : Fin 2), Sum.inr b1, ?_, ?_⟩ · dsimp [completeBipartiteGraph]; left; simp · ext x simp only [Finset.mem_symmDiff, Finset.mem_insert, Finset.mem_singleton] rw [hs] dsimp [u, two_token_kmn_lr_vertex] aesop · let u := two_token_kmn_lr_vertex (0 : Fin 2) b1 have hu : u ∈ S := by apply Finset.mem_insert_of_mem dsimp [lr_part] apply Finset.mem_image_of_mem simp [hb1] refine ⟨u, hu, ?_⟩ refine ⟨Sum.inl (0 : Fin 2), Sum.inr b2, ?_, ?_⟩ · dsimp [completeBipartiteGraph]; left; simp · ext x simp only [Finset.mem_symmDiff, Finset.mem_insert, Finset.mem_singleton] rw [hs] dsimp [u, two_token_kmn_lr_vertex] aesop
The cardinality of S is at most n - 2.
By `Finset.card_insert_le`, |S| ≤ |lr_part| + 1. By `Finset.card_image_le`, |lr_part| ≤ |Fin(n - 2) \ {z}|. By `Finset.card_erase_of_mem` and `Finset.mem_univ`, erasing z from Fin(n - 2) gives cardinality (n - 2) - 1. Combining these inequalities via linear arithmetic (`omega`) yields |S| ≤ (n - 2) - 1 + 1 = n - 2.
uses
Finset.card_insert_le,Finset.card_image_le,Finset.card_erase_of_mem,Finset.mem_univ· have h1 : S.card ≤ lr_part.card + 1 := Finset.card_insert_le ll lr_part have h2 : lr_part.card ≤ (Finset.univ.erase z).card := Finset.card_image_le have h3 : (Finset.univ.erase z).card = (n - 2) - 1 := by rw [Finset.card_erase_of_mem (Finset.mem_univ _)] simp omega
Finset.card_eq_two- A finite set has cardinality 2 if and only if it consists of two distinct elements.
Finset.pair_comm- The unordered pair {a, b} equals {b, a}.
two_token_k2_nminus2_has_dominating_set_finset_card_two_cases- Any 2-element subset of A ⊕ B is either two distinct elements of A, one element of A and one of B, or two distinct elements of B.
two_token_k2_nminus2_has_dominating_set_fin2_pair_eq- Any pair of distinct elements in Fin 2 embedded into Fin 2 ⊕ Fin k is equal to {0, 1}.
Subtype.ext- Two elements of a subtype are equal if their underlying values are equal.
Finset.mem_insert_self- An element a belongs to insert a s.
Finset.mem_insert_of_mem- If an element belongs to s, then it belongs to insert b s.
Finset.mem_image_of_mem- If a belongs to s, then f(a) belongs to Finset.image f s.
Finset.mem_symmDiff- An element belongs to the symmetric difference of two sets iff it belongs to one but not both.
Finset.mem_insert- An element belongs to insert b s iff it equals b or belongs to s.
Finset.mem_singleton- An element belongs to {a} iff it equals a.
Finset.card_insert_le- The cardinality of insert a s is at most the cardinality of s plus 1.
Finset.card_image_le- The cardinality of the image f(s) is at most the cardinality of s.
Finset.card_erase_of_mem- If an element a belongs to s, then erasing a decreases the cardinality by 1.
Finset.mem_univ- Every element of a finite type belongs to its universal finset univ.
- The verification that the symmetric difference of two 2-sets equals a specific edge pair in K_{2, n-2} is discharged automatically by `aesop` in several subcases.
- Vertices of the token graph are formally represented as subtypes `{ s : Finset (Fin 2 ⊕ Fin (n - 2)) // s.card = 2 }`, requiring `Subtype.ext` to establish vertex equalities.
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.
lemma two_token_k2_nminus2_has_dominating_set_finset_card_two_cases {A B : Type*} [DecidableEq A] [DecidableEq B] (s : Finset (A ⊕ B)) (hs : s.card = 2) : (∃ a1 a2 : A, a1 ≠ a2 ∧ s = {Sum.inl a1, Sum.inl a2}) ∨ (∃ (a : A) (b : B), s = {Sum.inl a, Sum.inr b}) ∨ (∃ b1 b2 : B, b1 ≠ b2 ∧ s = {Sum.inr b1, Sum.inr b2}) := by rw [Finset.card_eq_two] at hs rcases hs with ⟨x, y, hne, rfl⟩ rcases x with a1 | b1 <;> rcases y with a2 | b2 · left refine ⟨a1, a2, ?_, rfl⟩ rintro rfl; exact hne rfl · right; left; exact ⟨a1, b2, rfl⟩ · right; left; refine ⟨a2, b1, ?_⟩; rw [Finset.pair_comm] · right; right refine ⟨b1, b2, ?_, rfl⟩ rintro rfl; exact hne rfllemma two_token_k2_nminus2_has_dominating_set_fin2_pair_eq {k : ℕ} (a1 a2 : Fin 2) (hne : a1 ≠ a2) : ({Sum.inl a1, Sum.inl a2} : Finset (Fin 2 ⊕ Fin k)) = {Sum.inl (0 : Fin 2), Sum.inl (1 : Fin 2)} := by revert hne fin_cases a1 <;> fin_cases a2 · intro h; contradiction · intro _; rfl · intro _; rw [Finset.pair_comm]; rfl · intro h; contradiction/-- The 2-token graph F_2(K_{2,n-2}) has a dominating set of cardinality at most n - 2. -/theorem two_token_k2_nminus2_has_dominating_set (n : ℕ) (hn : 4 ≤ n) : ∃ S : Finset { s : Finset (Fin 2 ⊕ Fin (n - 2)) // s.card = 2 }, simple_graph_is_dominating (token_graph (completeBipartiteGraph (Fin 2) (Fin (n - 2))) 2) (S : Set _) ∧ S.card ≤ n - 2 := by have hk : 0 < n - 2 := by omega let z : Fin (n - 2) := ⟨0, hk⟩ let ll : { s : Finset (Fin 2 ⊕ Fin (n - 2)) // s.card = 2 } := two_token_kmn_ll_vertex (0 : Fin 2) (1 : Fin 2) (by decide) let lr_part := (Finset.univ.erase z).image (fun j => two_token_kmn_lr_vertex (0 : Fin 2) j) let S : Finset { s : Finset (Fin 2 ⊕ Fin (n - 2)) // s.card = 2 } := insert ll lr_part refine ⟨S, ?_, ?_⟩ · intro v rcases two_token_k2_nminus2_has_dominating_set_finset_card_two_cases v.val v.property with (⟨a1, a2, hne, hs⟩ | ⟨a, b, hs⟩ | ⟨b1, b2, hne, hs⟩) · -- Case LL left have h_eq : v = ll := by apply Subtype.ext dsimp [ll, two_token_kmn_ll_vertex] rw [hs] exact two_token_k2_nminus2_has_dominating_set_fin2_pair_eq a1 a2 hne rw [h_eq] exact Finset.mem_insert_self _ _ · -- Case LR fin_cases a · -- a = 0 by_cases hb : b = z · -- b = z subst hb right refine ⟨ll, Finset.mem_insert_self _ _, ?_⟩ refine ⟨Sum.inl (1 : Fin 2), Sum.inr z, ?_, ?_⟩ · dsimp [completeBipartiteGraph]; left; simp · ext x simp only [Finset.mem_symmDiff, Finset.mem_insert, Finset.mem_singleton] rw [hs] dsimp [ll, two_token_kmn_ll_vertex] aesop · -- b ≠ z left have h_eq : v = two_token_kmn_lr_vertex (0 : Fin 2) b := by apply Subtype.ext exact hs rw [h_eq] apply Finset.mem_insert_of_mem dsimp [lr_part] apply Finset.mem_image_of_mem simp [hb] · -- a = 1 right refine ⟨ll, Finset.mem_insert_self _ _, ?_⟩ refine ⟨Sum.inl (0 : Fin 2), Sum.inr b, ?_, ?_⟩ · dsimp [completeBipartiteGraph]; left; simp · ext x simp only [Finset.mem_symmDiff, Finset.mem_insert, Finset.mem_singleton] rw [hs] dsimp [ll, two_token_kmn_ll_vertex] aesop · -- Case RR right by_cases hb1 : b1 = z · have hb2 : b2 ≠ z := by intro h; subst h; subst hb1; exact hne rfl let u := two_token_kmn_lr_vertex (0 : Fin 2) b2 have hu : u ∈ S := by apply Finset.mem_insert_of_mem dsimp [lr_part] apply Finset.mem_image_of_mem simp [hb2] refine ⟨u, hu, ?_⟩ refine ⟨Sum.inl (0 : Fin 2), Sum.inr b1, ?_, ?_⟩ · dsimp [completeBipartiteGraph]; left; simp · ext x simp only [Finset.mem_symmDiff, Finset.mem_insert, Finset.mem_singleton] rw [hs] dsimp [u, two_token_kmn_lr_vertex] aesop · let u := two_token_kmn_lr_vertex (0 : Fin 2) b1 have hu : u ∈ S := by apply Finset.mem_insert_of_mem dsimp [lr_part] apply Finset.mem_image_of_mem simp [hb1] refine ⟨u, hu, ?_⟩ refine ⟨Sum.inl (0 : Fin 2), Sum.inr b2, ?_, ?_⟩ · dsimp [completeBipartiteGraph]; left; simp · ext x simp only [Finset.mem_symmDiff, Finset.mem_insert, Finset.mem_singleton] rw [hs] dsimp [u, two_token_kmn_lr_vertex] aesop · have h1 : S.card ≤ lr_part.card + 1 := Finset.card_insert_le ll lr_part have h2 : lr_part.card ≤ (Finset.univ.erase z).card := Finset.card_image_le have h3 : (Finset.univ.erase z).card = (n - 2) - 1 := by rw [Finset.card_erase_of_mem (Finset.mem_univ _)] simp omega