three_token_k2n_domination_number_four_ge
The domination number of the 3-token graph F_3(K_{2,4}) of the complete bipartite graph K_{2,4} is at least 4.
Statement
theorem three_token_k2n_domination_number_four_ge :
4 ≤ simple_graph_domination_number (token_graph (completeBipartiteGraph (Fin 2) (Fin 4)) 3)- 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 4
- bipartite_complement_adj_spectrum_and_lambda2Let H be an s-regular bipartite simple graph whose two parts V and W each have size m ≥ 2, and let G = K_{V,W} \ E(H) be its bipartite…
- three_token_k2n_domination_number_fourThe domination number of the 3-token graph F_3(K_{2,4}) of the complete bipartite graph K_{2,4} is 4.
- bipartite_complement_regularLet H be an s-regular bipartite simple graph on parts V and W of size m. Then its bipartite complement K_{V,W} \ H is (m - s)-regular.
- bipartite_complement_adj_charpoly_mulLet H be an s-regular graph contained in the complete bipartite graph on parts V, W of size m, and G = K_{V,W} minus H. Then…
The proof, explained
The proof partitions the vertices of the 3-token graph of K_{2,4} into two sets X and Y according to how many tokens lie in the size-2 part of the bipartite graph. Because the token graph is bipartite between X and Y, any dominating set must dominate both parts via its vertices and their cross-edges. Double counting the sizes and degrees yields a system of linear inequalities whose only integer solutions have size at least 4.
Decidability of graph relations
Establish decidability for complete bipartite graphs and token graphs.
instance three_token_k2n_domination_number_four_ge_decidableCompleteBipartiteAdj (V W : Type*) : DecidableRel (completeBipartiteGraph V W).Adj := by intro x y dsimp [completeBipartiteGraph] infer_instance abbrev three_token_k2n_domination_number_four_ge_V₀ := Fin 2 ⊕ Fin 4 abbrev three_token_k2n_domination_number_four_ge_G₀ : SimpleGraph three_token_k2n_domination_number_four_ge_V₀ := completeBipartiteGraph (Fin 2) (Fin 4) abbrev three_token_k2n_domination_number_four_ge_TG₀ : SimpleGraph { s : Finset three_token_k2n_domination_number_four_ge_V₀ // s.card = 3 } := token_graph three_token_k2n_domination_number_four_ge_G₀ 3 instance three_token_k2n_domination_number_four_ge_decidableTGAdj : DecidableRel three_token_k2n_domination_number_four_ge_TG₀.Adj := by intro x y dsimp [three_token_k2n_domination_number_four_ge_TG₀, token_graph] infer_instance
Properties of X and Y
Verify properties of X and Y by computation.
theorem three_token_k2n_domination_number_four_ge_X_card : three_token_k2n_domination_number_four_ge_X.card = 12 := by decide theorem three_token_k2n_domination_number_four_ge_Y_card : three_token_k2n_domination_number_four_ge_Y.card = 8 := by decide theorem three_token_k2n_domination_number_four_ge_deg_Y : ∀ y ∈ three_token_k2n_domination_number_four_ge_Y, (three_token_k2n_domination_number_four_ge_TG₀.neighborFinset y).card ≤ 6 := by decide theorem three_token_k2n_domination_number_four_ge_deg_X : ∀ x ∈ three_token_k2n_domination_number_four_ge_X, (three_token_k2n_domination_number_four_ge_TG₀.neighborFinset x).card ≤ 4 := by decide theorem three_token_k2n_domination_number_four_ge_neighbors_Y_in_X : ∀ y ∈ three_token_k2n_domination_number_four_ge_Y, ∀ v ∈ three_token_k2n_domination_number_four_ge_TG₀.neighborFinset y, v ∈ three_token_k2n_domination_number_four_ge_X := by decide theorem three_token_k2n_domination_number_four_ge_neighbors_X_in_Y : ∀ x ∈ three_token_k2n_domination_number_four_ge_X, ∀ v ∈ three_token_k2n_domination_number_four_ge_TG₀.neighborFinset x, v ∈ three_token_k2n_domination_number_four_ge_Y := by decide
X coverage
Show X is covered.
lemma three_token_k2n_domination_number_four_ge_X_sub (S : Finset three_token_k2n_domination_number_four_ge_V_TG) (hdom : simple_graph_is_dominating three_token_k2n_domination_number_four_ge_TG₀ (S : Set three_token_k2n_domination_number_four_ge_V_TG)) : three_token_k2n_domination_number_four_ge_X ⊆ (S ∩ three_token_k2n_domination_number_four_ge_X) ∪ (S ∩ three_token_k2n_domination_number_four_ge_Y).biUnion (fun u => three_token_k2n_domination_number_four_ge_TG₀.neighborFinset u) := by intro x hx rcases hdom x with hxS | ⟨u, huS, hadj⟩ · apply Finset.mem_union_left exact Finset.mem_inter.mpr ⟨hxS, hx⟩ · apply Finset.mem_union_right have hu_neigh : u ∈ three_token_k2n_domination_number_four_ge_TG₀.neighborFinset x := by rw [SimpleGraph.mem_neighborFinset] exact hadj.symm have huY : u ∈ three_token_k2n_domination_number_four_ge_Y := three_token_k2n_domination_number_four_ge_neighbors_X_in_Y x hx u hu_neigh rw [Finset.mem_biUnion] refine ⟨u, Finset.mem_inter.mpr ⟨huS, huY⟩, ?_⟩ rw [SimpleGraph.mem_neighborFinset] exact hadj
Y coverage
Show Y is covered.
lemma three_token_k2n_domination_number_four_ge_Y_sub (S : Finset three_token_k2n_domination_number_four_ge_V_TG) (hdom : simple_graph_is_dominating three_token_k2n_domination_number_four_ge_TG₀ (S : Set three_token_k2n_domination_number_four_ge_V_TG)) : three_token_k2n_domination_number_four_ge_Y ⊆ (S ∩ three_token_k2n_domination_number_four_ge_Y) ∪ (S ∩ three_token_k2n_domination_number_four_ge_X).biUnion (fun u => three_token_k2n_domination_number_four_ge_TG₀.neighborFinset u) := by intro y hy rcases hdom y with hyS | ⟨u, huS, hadj⟩ · apply Finset.mem_union_left exact Finset.mem_inter.mpr ⟨hyS, hy⟩ · apply Finset.mem_union_right have hu_neigh : u ∈ three_token_k2n_domination_number_four_ge_TG₀.neighborFinset y := by rw [SimpleGraph.mem_neighborFinset] exact hadj.symm have huX : u ∈ three_token_k2n_domination_number_four_ge_X := three_token_k2n_domination_number_four_ge_neighbors_Y_in_X y hy u hu_neigh rw [Finset.mem_biUnion] refine ⟨u, Finset.mem_inter.mpr ⟨huS, huX⟩, ?_⟩ rw [SimpleGraph.mem_neighborFinset] exact hadj
Card inequality for X
Bound card X.
lemma three_token_k2n_domination_number_four_ge_card_le_sum_X (S : Finset three_token_k2n_domination_number_four_ge_V_TG) (hdom : simple_graph_is_dominating three_token_k2n_domination_number_four_ge_TG₀ (S : Set three_token_k2n_domination_number_four_ge_V_TG)) : 12 ≤ (S ∩ three_token_k2n_domination_number_four_ge_X).card + 6 * (S ∩ three_token_k2n_domination_number_four_ge_Y).card := by have hsub := three_token_k2n_domination_number_four_ge_X_sub S hdom have h1 := Finset.card_le_card hsub have h2 := Finset.card_union_le (S ∩ three_token_k2n_domination_number_four_ge_X) ((S ∩ three_token_k2n_domination_number_four_ge_Y).biUnion (fun u => three_token_k2n_domination_number_four_ge_TG₀.neighborFinset u)) have h3 : ((S ∩ three_token_k2n_domination_number_four_ge_Y).biUnion (fun u => three_token_k2n_domination_number_four_ge_TG₀.neighborFinset u)).card ≤ (S ∩ three_token_k2n_domination_number_four_ge_Y).card * 6 := by apply Finset.card_biUnion_le_card_mul intro u hu exact three_token_k2n_domination_number_four_ge_deg_Y u (Finset.mem_inter.mp hu).2 rw [three_token_k2n_domination_number_four_ge_X_card] at h1 omega
Card inequality for Y
Bound card Y.
lemma three_token_k2n_domination_number_four_ge_card_le_sum_Y (S : Finset three_token_k2n_domination_number_four_ge_V_TG) (hdom : simple_graph_is_dominating three_token_k2n_domination_number_four_ge_TG₀ (S : Set three_token_k2n_domination_number_four_ge_V_TG)) : 8 ≤ 4 * (S ∩ three_token_k2n_domination_number_four_ge_X).card + (S ∩ three_token_k2n_domination_number_four_ge_Y).card := by have hsub := three_token_k2n_domination_number_four_ge_Y_sub S hdom have h1 := Finset.card_le_card hsub have h2 := Finset.card_union_le (S ∩ three_token_k2n_domination_number_four_ge_Y) ((S ∩ three_token_k2n_domination_number_four_ge_X).biUnion (fun u => three_token_k2n_domination_number_four_ge_TG₀.neighborFinset u)) have h3 : ((S ∩ three_token_k2n_domination_number_four_ge_X).biUnion (fun u => three_token_k2n_domination_number_four_ge_TG₀.neighborFinset u)).card ≤ (S ∩ three_token_k2n_domination_number_four_ge_X).card * 4 := by apply Finset.card_biUnion_le_card_mul intro u hu exact three_token_k2n_domination_number_four_ge_deg_X u (Finset.mem_inter.mp hu).2 rw [three_token_k2n_domination_number_four_ge_Y_card] at h1 omega
Domination number lower bound for S
Any dominating set S has size at least 4.
lemma three_token_k2n_domination_number_four_ge_dom_ge_four (S : Finset three_token_k2n_domination_number_four_ge_V_TG) (hdom : simple_graph_is_dominating three_token_k2n_domination_number_four_ge_TG₀ (S : Set three_token_k2n_domination_number_four_ge_V_TG)) : 4 ≤ S.card := by have hd : Disjoint (S ∩ three_token_k2n_domination_number_four_ge_X) (S ∩ three_token_k2n_domination_number_four_ge_Y) := by rw [Finset.disjoint_iff_ne] intro a ha b hb simp only [Finset.mem_inter, three_token_k2n_domination_number_four_ge_X, three_token_k2n_domination_number_four_ge_Y, Finset.mem_filter] at ha hb rintro rfl exact hb.2.2 ha.2.2 have hu : S = (S ∩ three_token_k2n_domination_number_four_ge_X) ∪ (S ∩ three_token_k2n_domination_number_four_ge_Y) := by ext a simp only [Finset.mem_union, Finset.mem_inter, three_token_k2n_domination_number_four_ge_X, three_token_k2n_domination_number_four_ge_Y, Finset.mem_filter, Finset.mem_univ, true_and] tauto have hcard : S.card = (S ∩ three_token_k2n_domination_number_four_ge_X).card + (S ∩ three_token_k2n_domination_number_four_ge_Y).card := by conv_lhs => rw [hu] exact Finset.card_union_of_disjoint hd have hX := three_token_k2n_domination_number_four_ge_card_le_sum_X S hdom have hY := three_token_k2n_domination_number_four_ge_card_le_sum_Y S hdom omega
Main theorem
The domination number is at least 4.
/-- The domination number of the 3-token graph F_3(K_{2,4}) is at least 4. -/ theorem three_token_k2n_domination_number_four_ge : 4 ≤ simple_graph_domination_number (token_graph (completeBipartiteGraph (Fin 2) (Fin 4)) 3) := by unfold simple_graph_domination_number have hne : {k | ∃ S : Finset three_token_k2n_domination_number_four_ge_V_TG, simple_graph_is_dominating three_token_k2n_domination_number_four_ge_TG₀ ↑S ∧ S.card = k}.Nonempty := by use (Finset.univ : Finset three_token_k2n_domination_number_four_ge_V_TG).card refine ⟨Finset.univ, ?_, rfl⟩ intro v left simp have hmem := Nat.sInf_mem hne dsimp at hmem rcases hmem with ⟨S, hdom, hcard⟩ rw [← hcard] exact three_token_k2n_domination_number_four_ge_dom_ge_four S hdom
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.
instance three_token_k2n_domination_number_four_ge_decidableCompleteBipartiteAdj (V W : Type*) : DecidableRel (completeBipartiteGraph V W).Adj := by intro x y dsimp [completeBipartiteGraph] infer_instanceabbrev three_token_k2n_domination_number_four_ge_V₀ := Fin 2 ⊕ Fin 4abbrev three_token_k2n_domination_number_four_ge_G₀ : SimpleGraph three_token_k2n_domination_number_four_ge_V₀ := completeBipartiteGraph (Fin 2) (Fin 4)abbrev three_token_k2n_domination_number_four_ge_TG₀ : SimpleGraph { s : Finset three_token_k2n_domination_number_four_ge_V₀ // s.card = 3 } := token_graph three_token_k2n_domination_number_four_ge_G₀ 3instance three_token_k2n_domination_number_four_ge_decidableTGAdj : DecidableRel three_token_k2n_domination_number_four_ge_TG₀.Adj := by intro x y dsimp [three_token_k2n_domination_number_four_ge_TG₀, token_graph] infer_instancedef three_token_k2n_domination_number_four_ge_c (s : Finset three_token_k2n_domination_number_four_ge_V₀) : ℕ := (s.filter (fun x => x.isLeft)).cardabbrev three_token_k2n_domination_number_four_ge_V_TG := { s : Finset three_token_k2n_domination_number_four_ge_V₀ // s.card = 3 }def three_token_k2n_domination_number_four_ge_X : Finset three_token_k2n_domination_number_four_ge_V_TG := Finset.univ.filter (fun s => three_token_k2n_domination_number_four_ge_c s.val = 1)def three_token_k2n_domination_number_four_ge_Y : Finset three_token_k2n_domination_number_four_ge_V_TG := Finset.univ.filter (fun s => three_token_k2n_domination_number_four_ge_c s.val ≠ 1)theorem three_token_k2n_domination_number_four_ge_X_card : three_token_k2n_domination_number_four_ge_X.card = 12 := by decidetheorem three_token_k2n_domination_number_four_ge_Y_card : three_token_k2n_domination_number_four_ge_Y.card = 8 := by decidetheorem three_token_k2n_domination_number_four_ge_deg_Y : ∀ y ∈ three_token_k2n_domination_number_four_ge_Y, (three_token_k2n_domination_number_four_ge_TG₀.neighborFinset y).card ≤ 6 := by decidetheorem three_token_k2n_domination_number_four_ge_deg_X : ∀ x ∈ three_token_k2n_domination_number_four_ge_X, (three_token_k2n_domination_number_four_ge_TG₀.neighborFinset x).card ≤ 4 := by decidetheorem three_token_k2n_domination_number_four_ge_neighbors_Y_in_X : ∀ y ∈ three_token_k2n_domination_number_four_ge_Y, ∀ v ∈ three_token_k2n_domination_number_four_ge_TG₀.neighborFinset y, v ∈ three_token_k2n_domination_number_four_ge_X := by decidetheorem three_token_k2n_domination_number_four_ge_neighbors_X_in_Y : ∀ x ∈ three_token_k2n_domination_number_four_ge_X, ∀ v ∈ three_token_k2n_domination_number_four_ge_TG₀.neighborFinset x, v ∈ three_token_k2n_domination_number_four_ge_Y := by decidelemma three_token_k2n_domination_number_four_ge_X_sub (S : Finset three_token_k2n_domination_number_four_ge_V_TG) (hdom : simple_graph_is_dominating three_token_k2n_domination_number_four_ge_TG₀ (S : Set three_token_k2n_domination_number_four_ge_V_TG)) : three_token_k2n_domination_number_four_ge_X ⊆ (S ∩ three_token_k2n_domination_number_four_ge_X) ∪ (S ∩ three_token_k2n_domination_number_four_ge_Y).biUnion (fun u => three_token_k2n_domination_number_four_ge_TG₀.neighborFinset u) := by intro x hx rcases hdom x with hxS | ⟨u, huS, hadj⟩ · apply Finset.mem_union_left exact Finset.mem_inter.mpr ⟨hxS, hx⟩ · apply Finset.mem_union_right have hu_neigh : u ∈ three_token_k2n_domination_number_four_ge_TG₀.neighborFinset x := by rw [SimpleGraph.mem_neighborFinset] exact hadj.symm have huY : u ∈ three_token_k2n_domination_number_four_ge_Y := three_token_k2n_domination_number_four_ge_neighbors_X_in_Y x hx u hu_neigh rw [Finset.mem_biUnion] refine ⟨u, Finset.mem_inter.mpr ⟨huS, huY⟩, ?_⟩ rw [SimpleGraph.mem_neighborFinset] exact hadjlemma three_token_k2n_domination_number_four_ge_Y_sub (S : Finset three_token_k2n_domination_number_four_ge_V_TG) (hdom : simple_graph_is_dominating three_token_k2n_domination_number_four_ge_TG₀ (S : Set three_token_k2n_domination_number_four_ge_V_TG)) : three_token_k2n_domination_number_four_ge_Y ⊆ (S ∩ three_token_k2n_domination_number_four_ge_Y) ∪ (S ∩ three_token_k2n_domination_number_four_ge_X).biUnion (fun u => three_token_k2n_domination_number_four_ge_TG₀.neighborFinset u) := by intro y hy rcases hdom y with hyS | ⟨u, huS, hadj⟩ · apply Finset.mem_union_left exact Finset.mem_inter.mpr ⟨hyS, hy⟩ · apply Finset.mem_union_right have hu_neigh : u ∈ three_token_k2n_domination_number_four_ge_TG₀.neighborFinset y := by rw [SimpleGraph.mem_neighborFinset] exact hadj.symm have huX : u ∈ three_token_k2n_domination_number_four_ge_X := three_token_k2n_domination_number_four_ge_neighbors_Y_in_X y hy u hu_neigh rw [Finset.mem_biUnion] refine ⟨u, Finset.mem_inter.mpr ⟨huS, huX⟩, ?_⟩ rw [SimpleGraph.mem_neighborFinset] exact hadjlemma three_token_k2n_domination_number_four_ge_card_le_sum_X (S : Finset three_token_k2n_domination_number_four_ge_V_TG) (hdom : simple_graph_is_dominating three_token_k2n_domination_number_four_ge_TG₀ (S : Set three_token_k2n_domination_number_four_ge_V_TG)) : 12 ≤ (S ∩ three_token_k2n_domination_number_four_ge_X).card + 6 * (S ∩ three_token_k2n_domination_number_four_ge_Y).card := by have hsub := three_token_k2n_domination_number_four_ge_X_sub S hdom have h1 := Finset.card_le_card hsub have h2 := Finset.card_union_le (S ∩ three_token_k2n_domination_number_four_ge_X) ((S ∩ three_token_k2n_domination_number_four_ge_Y).biUnion (fun u => three_token_k2n_domination_number_four_ge_TG₀.neighborFinset u)) have h3 : ((S ∩ three_token_k2n_domination_number_four_ge_Y).biUnion (fun u => three_token_k2n_domination_number_four_ge_TG₀.neighborFinset u)).card ≤ (S ∩ three_token_k2n_domination_number_four_ge_Y).card * 6 := by apply Finset.card_biUnion_le_card_mul intro u hu exact three_token_k2n_domination_number_four_ge_deg_Y u (Finset.mem_inter.mp hu).2 rw [three_token_k2n_domination_number_four_ge_X_card] at h1 omegalemma three_token_k2n_domination_number_four_ge_card_le_sum_Y (S : Finset three_token_k2n_domination_number_four_ge_V_TG) (hdom : simple_graph_is_dominating three_token_k2n_domination_number_four_ge_TG₀ (S : Set three_token_k2n_domination_number_four_ge_V_TG)) : 8 ≤ 4 * (S ∩ three_token_k2n_domination_number_four_ge_X).card + (S ∩ three_token_k2n_domination_number_four_ge_Y).card := by have hsub := three_token_k2n_domination_number_four_ge_Y_sub S hdom have h1 := Finset.card_le_card hsub have h2 := Finset.card_union_le (S ∩ three_token_k2n_domination_number_four_ge_Y) ((S ∩ three_token_k2n_domination_number_four_ge_X).biUnion (fun u => three_token_k2n_domination_number_four_ge_TG₀.neighborFinset u)) have h3 : ((S ∩ three_token_k2n_domination_number_four_ge_X).biUnion (fun u => three_token_k2n_domination_number_four_ge_TG₀.neighborFinset u)).card ≤ (S ∩ three_token_k2n_domination_number_four_ge_X).card * 4 := by apply Finset.card_biUnion_le_card_mul intro u hu exact three_token_k2n_domination_number_four_ge_deg_X u (Finset.mem_inter.mp hu).2 rw [three_token_k2n_domination_number_four_ge_Y_card] at h1 omegalemma three_token_k2n_domination_number_four_ge_dom_ge_four (S : Finset three_token_k2n_domination_number_four_ge_V_TG) (hdom : simple_graph_is_dominating three_token_k2n_domination_number_four_ge_TG₀ (S : Set three_token_k2n_domination_number_four_ge_V_TG)) : 4 ≤ S.card := by have hd : Disjoint (S ∩ three_token_k2n_domination_number_four_ge_X) (S ∩ three_token_k2n_domination_number_four_ge_Y) := by rw [Finset.disjoint_iff_ne] intro a ha b hb simp only [Finset.mem_inter, three_token_k2n_domination_number_four_ge_X, three_token_k2n_domination_number_four_ge_Y, Finset.mem_filter] at ha hb rintro rfl exact hb.2.2 ha.2.2 have hu : S = (S ∩ three_token_k2n_domination_number_four_ge_X) ∪ (S ∩ three_token_k2n_domination_number_four_ge_Y) := by ext a simp only [Finset.mem_union, Finset.mem_inter, three_token_k2n_domination_number_four_ge_X, three_token_k2n_domination_number_four_ge_Y, Finset.mem_filter, Finset.mem_univ, true_and] tauto have hcard : S.card = (S ∩ three_token_k2n_domination_number_four_ge_X).card + (S ∩ three_token_k2n_domination_number_four_ge_Y).card := by conv_lhs => rw [hu] exact Finset.card_union_of_disjoint hd have hX := three_token_k2n_domination_number_four_ge_card_le_sum_X S hdom have hY := three_token_k2n_domination_number_four_ge_card_le_sum_Y S hdom omega/-- The domination number of the 3-token graph F_3(K_{2,4}) is at least 4. -/theorem three_token_k2n_domination_number_four_ge : 4 ≤ simple_graph_domination_number (token_graph (completeBipartiteGraph (Fin 2) (Fin 4)) 3) := by unfold simple_graph_domination_number have hne : {k | ∃ S : Finset three_token_k2n_domination_number_four_ge_V_TG, simple_graph_is_dominating three_token_k2n_domination_number_four_ge_TG₀ ↑S ∧ S.card = k}.Nonempty := by use (Finset.univ : Finset three_token_k2n_domination_number_four_ge_V_TG).card refine ⟨Finset.univ, ?_, rfl⟩ intro v left simp have hmem := Nat.sInf_mem hne dsimp at hmem rcases hmem with ⟨S, hdom, hcard⟩ rw [← hcard] exact three_token_k2n_domination_number_four_ge_dom_ge_four S hdom