two_token_domination_number_odd_p3_matching_le
Let 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 1. Then the domination number of the 2-token graph F_2(G) is at most (Fintype.card V + 1) / 2.
Statement
open scoped Classical in theorem two_token_domination_number_odd_p3_matching_le {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (hdeg : ∃ 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 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
Let $V$ be a finite type with decidable equality, and let $G$ be a simple graph on $V$. Suppose there exists a vertex $v \in V$ whose degree in the complement graph $G^c$ is $2$, and such that every vertex $u \neq v$ has degree $1$ in $G^c$. Then the domination number of the 2-token graph of $G$ is at most $(|V| + 1) / 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 complement graph Gᶜ decomposes into a 3-vertex path P₃ on {x₁, x₂, x₃} centered at x₂ and a disjoint 1-factor (perfect matching) on the remaining |V| - 3 vertices W. An explicit dominating set D of the 2-token graph F₂(G) is constructed consisting of the (|V| - 3) / 2 matching edges on W together with two edges from the path, e₁ = {x₁, x₂} and e₂ = {x₁, x₃}, for a total size of (|V| + 1) / 2. Every pair {a, b} intersecting W is dominated by the matching edge containing that vertex, while every pair within {x₁, x₂, x₃} is either in D or dominated by e₁ via the edge {x₁, x₃} in G. Thus D dominates F₂(G), proving that the domination number is at most (|V| + 1) / 2.
For distinct vertices a, b, x, the symmetric difference of {a, x} and {a, b} is {b, x}.
By extensionality on an arbitrary element c, expanding the definition of symmetric difference into boolean combinations and checking each of the mutually exclusive cases c = a, c = x, c = b, or none of these.
uses
Finset.mem_symmDiff,Finset.mem_insert,Finset.mem_singletonext c rw [Finset.mem_symmDiff] simp only [Finset.mem_insert, Finset.mem_singleton] by_cases hca : c = a · subst hca simp [hab, hax] · by_cases hcx : c = x · subst hcx simp [hbx.symm, hax.symm] · by_cases hcb : c = b · subst hcb simp [hab.symm, hbx] · simp [hca, hcx, hcb]
There is a unique vertex x₂ of degree 2 in Gᶜ, and every other vertex u ≠ x₂ has degree 1 in Gᶜ with a unique neighbor.
From the degree hypothesis, we obtain x₂ of degree 2 and the property that all other vertices have degree 1 in Gᶜ. For each u ≠ x₂, the cardinality of its neighbor finset in Gᶜ is 1, which means there is a unique vertex w adjacent to u in Gᶜ.
uses
SimpleGraph.card_neighborFinset_eq_degree,Finset.card_eq_one.mp,SimpleGraph.mem_neighborFinsetclassical obtain ⟨x2, hx2_deg, hothers⟩ := hdeg have hex : ∀ u, u ≠ x2 → ∃! w, Gᶜ.Adj u w := by intro u hu have h1 : (Gᶜ.neighborFinset u).card = 1 := by rw [SimpleGraph.card_neighborFinset_eq_degree, hothers u hu] obtain ⟨w, hw⟩ := Finset.card_eq_one.mp h1 refine ⟨w, ?_, ?_⟩ · have : w ∈ Gᶜ.neighborFinset u := by rw [hw]; simp exact (SimpleGraph.mem_neighborFinset _ _ _).mp this · intro y hy have : y ∈ Gᶜ.neighborFinset u := (SimpleGraph.mem_neighborFinset _ _ _).mpr hy rw [hw] at this simpa using this
The map p : V → V sends each v ≠ x₂ to its unique neighbor in Gᶜ.
We define p(v) by choosing the unique neighbor of v in Gᶜ when v ≠ x₂, and setting p(x₂) = x₂. By construction, p(v) is adjacent to v in Gᶜ and is its unique neighbor.
uses
dif_neg,Classical.choose_speclet p : V → V := fun v => if h : v = x2 then x2 else Classical.choose (hex v h) have hp_def : ∀ v (hv : v ≠ x2), p v = Classical.choose (hex v hv) := by intro v hv dsimp [p] rw [dif_neg hv] have hp_adj : ∀ v (hv : v ≠ x2), Gᶜ.Adj v (p v) := by intro v hv rw [hp_def v hv] exact (Classical.choose_spec (hex v hv)).1 have hp_uniq : ∀ v (hv : v ≠ x2) w, Gᶜ.Adj v w → w = p v := by intro v hv w hw rw [hp_def v hv] exact (Classical.choose_spec (hex v hv)).2 w hw
The vertex x₂ has two distinct neighbors x₁, x₃ in Gᶜ, and p(x₁) = x₂ and p(x₃) = x₂.
Since the degree of x₂ in Gᶜ is 2, its neighbor finset has cardinality 2, yielding two distinct neighbors x₁ and x₃. By uniqueness of the neighbor of any vertex of degree 1, p(x₁) = x₂ and p(x₃) = x₂.
uses
SimpleGraph.card_neighborFinset_eq_degree,Finset.card_eq_two.mp,SimpleGraph.mem_neighborFinset,SimpleGraph.ne_of_adjhave h2 : (Gᶜ.neighborFinset x2).card = 2 := by rw [SimpleGraph.card_neighborFinset_eq_degree, hx2_deg] obtain ⟨x1, x3, hx13_ne, hx2_nbrs⟩ := Finset.card_eq_two.mp h2 have hx1_mem : x1 ∈ Gᶜ.neighborFinset x2 := by rw [hx2_nbrs]; simp have hx3_mem : x3 ∈ Gᶜ.neighborFinset x2 := by rw [hx2_nbrs]; simp have hx21_adj : Gᶜ.Adj x2 x1 := (SimpleGraph.mem_neighborFinset _ _ _).mp hx1_mem have hx23_adj : Gᶜ.Adj x2 x3 := (SimpleGraph.mem_neighborFinset _ _ _).mp hx3_mem have hx12_ne : x1 ≠ x2 := ((Gᶜ).ne_of_adj hx21_adj).symm have hx32_ne : x3 ≠ x2 := ((Gᶜ).ne_of_adj hx23_adj).symm have hpx1 : p x1 = x2 := (hp_uniq x1 hx12_ne x2 hx21_adj.symm).symm have hpx3 : p x3 = x2 := (hp_uniq x3 hx32_ne x2 hx23_adj.symm).symm
On W = V \ {x₁, x₂, x₃}, the map p is a fixed-point-free involution that preserves W.
For any u ∈ W, its neighbor p(u) cannot be x₁, x₂, or x₃ because that would force u to equal x₂ or {x₁, x₃}, contradicting u ∈ W; hence p(u) ∈ W. Since u is adjacent to p(u) in Gᶜ and p(u) ≠ x₂, the unique neighbor of p(u) is u, so p(p(u)) = u. As Gᶜ is loopless, p(u) ≠ u.
uses
Finset.mem_filter,Finset.mem_univ,SimpleGraph.mem_neighborFinset,Finset.mem_insert,Finset.mem_singleton,SimpleGraph.ne_of_adjlet W : Finset V := Finset.univ.filter (fun v => v ≠ x1 ∧ v ≠ x2 ∧ v ≠ x3) have hpW : ∀ u ∈ W, p u ∈ W := by intro u hu rw [Finset.mem_filter] at hu ⊢ obtain ⟨-, hu1, hu2, hu3⟩ := hu have hpadj := hp_adj u hu2 refine ⟨Finset.mem_univ _, ?_, ?_, ?_⟩ · intro h have h1 : Gᶜ.Adj x1 u := by rw [h] at hpadj; exact hpadj.symm have := hp_uniq x1 hx12_ne u h1 rw [hpx1] at this exact hu2 this · intro h have h2 : Gᶜ.Adj x2 u := by rw [h] at hpadj; exact hpadj.symm have hmem : u ∈ Gᶜ.neighborFinset x2 := (SimpleGraph.mem_neighborFinset _ _ _).mpr h2 rw [hx2_nbrs] at hmem simp only [Finset.mem_insert, Finset.mem_singleton] at hmem rcases hmem with rfl | rfl · exact hu1 rfl · exact hu3 rfl · intro h have h3 : Gᶜ.Adj x3 u := by rw [h] at hpadj; exact hpadj.symm have := hp_uniq x3 hx32_ne u h3 rw [hpx3] at this exact hu2 this have hpinvol : ∀ u ∈ W, p (p u) = u := by intro u hu have hpuW := hpW u hu rw [Finset.mem_filter] at hu hpuW have hadj := (hp_adj u hu.2.2.1).symm exact (hp_uniq (p u) hpuW.2.2.1 u hadj).symm have hpne : ∀ u ∈ W, p u ≠ u := by intro u hu rw [Finset.mem_filter] at hu intro h exact (Gᶜ).ne_of_adj (hp_adj u hu.2.2.1) h.symm
Distinct non-adjacent vertices in Gᶜ are adjacent in G; in particular, x₁ and x₃ are adjacent in G.
By definition of the graph complement, any two distinct vertices not adjacent in Gᶜ must be adjacent in G. Since the only neighbor of x₁ in Gᶜ is x₂ ≠ x₃, the vertices x₁ and x₃ are not adjacent in Gᶜ, so they are adjacent in G.
have hGadj : ∀ u v : V, u ≠ v → ¬ Gᶜ.Adj u v → G.Adj u v := by intro u v huv hc by_contra h exact hc ⟨huv, h⟩ have hx13_Gadj : G.Adj x1 x3 := by apply hGadj x1 x3 hx13_ne intro hc have := hp_uniq x1 hx12_ne x3 hc rw [hpx1] at this exact hx32_ne this
The set DW = { {u, p(u)} | u ∈ W } of matching edges on W has cardinality |W| / 2.
We define f : V → {s : Finset V // |s| = 2} mapping each u ∈ W to {u, p(u)}. Since p is a fixed-point-free involution on W, the fiber of f over any edge in DW consists of exactly 2 vertices {u, p(u)}. By fiberwise summation, |W| = 2 |DW|, so |DW| = |W| / 2.
uses
Finset.card_pair,Finset.mem_filter,Finset.mem_insert,Finset.mem_singleton,dif_pos,Subtype.ext,Finset.pair_comm,Finset.card_eq_sum_card_fiberwise,Finset.sum_congr,Finset.sum_const,Nat.mul_div_cancellet f : V → {s : Finset V // s.card = 2} := fun u => if h : u ∈ W then ⟨{u, p u}, Finset.card_pair (hpne u h).symm⟩ else ⟨{x1, x2}, Finset.card_pair hx12_ne⟩ have hfib : ∀ u ∈ W, (W.filter (fun v => f v = f u)) = ({u, p u} : Finset V) := by intro u hu ext v simp only [Finset.mem_filter, Finset.mem_insert, Finset.mem_singleton] constructor · rintro ⟨hvW, heq⟩ have huW := hu dsimp [f] at heq rw [dif_pos hvW, dif_pos huW] at heq have hmem : v ∈ (⟨{v, p v}, Finset.card_pair (hpne v hvW).symm⟩ : {s : Finset V // s.card = 2}).val := by simp rw [heq] at hmem simpa using hmem · rintro (rfl | rfl) · exact ⟨hu, rfl⟩ · refine ⟨hpW u hu, ?_⟩ dsimp [f] rw [dif_pos (hpW u hu), dif_pos hu] apply Subtype.ext change ({p u, p (p u)} : Finset V) = {u, p u} rw [hpinvol u hu, Finset.pair_comm] let DW : Finset {s : Finset V // s.card = 2} := W.image f have hmaps : Set.MapsTo f (↑W) (↑DW) := by intro x hx exact Finset.mem_image.mpr ⟨x, hx, rfl⟩ have hsum := Finset.card_eq_sum_card_fiberwise hmaps have hfiber2 : ∀ b ∈ DW, (W.filter (fun a => f a = b)).card = 2 := by intro b hb obtain ⟨u, hu, rfl⟩ := Finset.mem_image.mp hb rw [hfib u hu, Finset.card_pair (hpne u hu).symm] have h1 : W.card = DW.card * 2 := by rw [hsum, Finset.sum_congr rfl hfiber2] simp [Finset.sum_const] have hDWcard : DW.card = W.card / 2 := by rw [h1, Nat.mul_div_cancel _ (by norm_num : 0 < 2)]
The set {x₁, x₂, x₃} has cardinality 3, so |W| = |V| - 3.
Because x₁, x₂, x₃ are pairwise distinct, {x₁, x₂, x₃} has 3 elements. Since W is the complement of this set in V, |W| = |V| - 3.
uses
Finset.card_insert_of_notMem,Finset.card_singleton,Finset.card_sdiff_of_subset,Finset.subset_univ,Finset.card_univ,Finset.card_le_cardhave hx23 : x2 ∉ ({x3} : Finset V) := by simp [hx32_ne.symm] have hx123 : x1 ∉ ({x2, x3} : Finset V) := by simp [hx12_ne, hx13_ne] have hcardX : ({x1, x2, x3} : Finset V).card = 3 := by rw [Finset.card_insert_of_notMem hx123, Finset.card_insert_of_notMem hx23, Finset.card_singleton] have hW_compl : W = Finset.univ \ {x1, x2, x3} := by ext v simp [W] have hWcard : W.card = Fintype.card V - 3 := by rw [hW_compl, Finset.card_sdiff_of_subset (Finset.subset_univ _), Finset.card_univ, hcardX] have hV3 : 3 ≤ Fintype.card V := by rw [← Finset.card_univ, ← hcardX] exact Finset.card_le_card (Finset.subset_univ _)
The candidate dominating set D = DW ∪ {e₁, e₂}, with e₁ = {x₁, x₂} and e₂ = {x₁, x₃}, has size (|V| + 1) / 2.
The edges e₁ and e₂ are not in DW because all vertices in edges of DW belong to W, which is disjoint from {x₁, x₂, x₃}. Since x₂ ≠ x₃, e₁ ≠ e₂. Therefore, |D| = |DW| + 2 = (|V| - 3) / 2 + 2 = (|V| + 1) / 2.
uses
Finset.card_pair,dif_pos,Finset.mem_insert,Finset.mem_singleton,Finset.mem_filter,Finset.card_insert_of_notMemlet e1 : {s : Finset V // s.card = 2} := ⟨{x1, x2}, Finset.card_pair hx12_ne⟩ let e2 : {s : Finset V // s.card = 2} := ⟨{x1, x3}, Finset.card_pair hx13_ne⟩ have he1_not_DW : e1 ∉ DW := by intro hmem obtain ⟨u, huW, heq⟩ := Finset.mem_image.mp hmem have huW_prop : u ∈ W := huW dsimp [f] at heq rw [dif_pos huW] at heq have hval : ({u, p u} : Finset V) = {x1, x2} := Subtype.ext_iff.mp heq have hx1 : x1 ∈ ({u, p u} : Finset V) := by rw [hval]; simp simp only [Finset.mem_insert, Finset.mem_singleton] at hx1 rw [Finset.mem_filter] at huW_prop rcases hx1 with rfl | hpu · exact huW_prop.2.1 rfl · have hpuW := hpW u huW rw [Finset.mem_filter] at hpuW exact hpuW.2.1 hpu.symm have he2_not_DW : e2 ∉ DW := by intro hmem obtain ⟨u, huW, heq⟩ := Finset.mem_image.mp hmem have huW_prop : u ∈ W := huW dsimp [f] at heq rw [dif_pos huW] at heq have hval : ({u, p u} : Finset V) = {x1, x3} := Subtype.ext_iff.mp heq have hx1 : x1 ∈ ({u, p u} : Finset V) := by rw [hval]; simp simp only [Finset.mem_insert, Finset.mem_singleton] at hx1 rw [Finset.mem_filter] at huW_prop rcases hx1 with rfl | hpu · exact huW_prop.2.1 rfl · have hpuW := hpW u huW rw [Finset.mem_filter] at hpuW exact hpuW.2.1 hpu.symm have he12_ne : e1 ≠ e2 := by intro h have hval : e1.val = e2.val := by rw [h] change ({x1, x2} : Finset V) = {x1, x3} at hval have hx2 : x2 ∈ ({x1, x3} : Finset V) := by rw [← hval]; simp simp only [Finset.mem_insert, Finset.mem_singleton] at hx2 rcases hx2 with rfl | rfl · exact hx12_ne.symm rfl · exact hx32_ne.symm rfl let D : Finset {s : Finset V // s.card = 2} := insert e1 (insert e2 DW) have he1_not : e1 ∉ insert e2 DW := by simp [he12_ne, he1_not_DW] have hDcard : D.card = 2 + DW.card := by dsimp [D] rw [Finset.card_insert_of_notMem he1_not, Finset.card_insert_of_notMem he2_not_DW] omega have hD_total : D.card = (Fintype.card V + 1) / 2 := by rw [hDcard, hDWcard, hWcard] omega
Any pair {a, b} with a ∈ W is either in D or adjacent in F₂(G) to {a, p(a)} ∈ D.
If b = p(a), then {a, b} = {a, p(a)} ∈ DW ⊆ D. If b ≠ p(a), the symmetric difference of {a, p(a)} and {a, b} is {b, p(a)}. Since the only neighbor of p(a) in Gᶜ is a ≠ b, b and p(a) are not adjacent in Gᶜ, hence adjacent in G. Thus {a, p(a)} is adjacent to {a, b} in F₂(G).
uses
Finset.card_pair,dif_pos,Subtype.ext,Finset.mem_filter,two_token_domination_number_odd_p3_matching_le_symmDiff_pair_pairhave hdom_u : ∀ a b : V, (hab : a ≠ b) → a ∈ W → (⟨{a, b}, Finset.card_pair hab⟩ : {s : Finset V // s.card = 2}) ∈ D ∨ ∃ t ∈ D, (token_graph G 2).Adj t ⟨{a, b}, Finset.card_pair hab⟩ := by intro a b hab haW have hfa_DW : f a ∈ DW := Finset.mem_image.mpr ⟨a, haW, rfl⟩ have hfa_D : f a ∈ D := by simp [D, hfa_DW] have hfa_val : (f a).val = {a, p a} := by dsimp [f] rw [dif_pos haW] by_cases hb : b = p a · left subst hb have heq : (⟨{a, p a}, Finset.card_pair hab⟩ : {s : Finset V // s.card = 2}) = f a := by apply Subtype.ext rw [hfa_val] rw [heq] exact hfa_D · right refine ⟨f a, hfa_D, b, p a, ?_, ?_⟩ · apply hGadj · exact hb · intro hc have hpadj : Gᶜ.Adj (p a) b := hc.symm have hpaW := hpW a haW rw [Finset.mem_filter] at hpaW have huniq := hp_uniq (p a) hpaW.2.2.1 b hpadj rw [hpinvol a haW] at huniq exact hab huniq.symm · rw [hfa_val] change symmDiff ({a, p a} : Finset V) {a, b} = {b, p a} have hpa_ne_a : a ≠ p a := (hpne a haW).symm exact two_token_domination_number_odd_p3_matching_le_symmDiff_pair_pair a b (p a) hab hpa_ne_a hb have he1_D : e1 ∈ D := by simp [D] have he2_D : e2 ∈ D := by simp [D]
The set D is a dominating set of the 2-token graph F₂(G).
Given any 2-element set {a, b}, if either a ∈ W or b ∈ W, it is dominated by D by the previous claim. Otherwise, {a, b} ⊆ {x₁, x₂, x₃}. If {a, b} is {x₁, x₂} = e₁ or {x₁, x₃} = e₂, it belongs to D. If {a, b} = {x₂, x₃}, its symmetric difference with e₁ = {x₁, x₂} ∈ D is {x₁, x₃}, and x₁ is adjacent to x₃ in G, so e₁ dominates {x₂, x₃}.
uses
Finset.card_eq_two.mp,Finset.card_pair,Subtype.ext,Finset.pair_comm,Finset.mem_filter,Finset.mem_univ,two_token_domination_number_odd_p3_matching_le_symmDiff_pair_pairhave 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 haW : a ∈ W · exact hdom_u a b hab haW · by_cases hbW : b ∈ W · have hsymm := hdom_u b a hab.symm hbW have hpair_eq : (⟨{b, a}, Finset.card_pair hab.symm⟩ : {s : Finset V // s.card = 2}) = ⟨{a, b}, Finset.card_pair hab⟩ := by apply Subtype.ext exact Finset.pair_comm b a rw [hpair_eq] at hsymm exact hsymm · have ha_cases : a = x1 ∨ a = x2 ∨ a = x3 := by simp only [W, Finset.mem_filter, Finset.mem_univ, true_and, not_and] at haW tauto have hb_cases : b = x1 ∨ b = x2 ∨ b = x3 := by simp only [W, Finset.mem_filter, Finset.mem_univ, true_and, not_and] at hbW tauto have hcases : (a = x1 ∧ b = x2) ∨ (a = x2 ∧ b = x1) ∨ (a = x1 ∧ b = x3) ∨ (a = x3 ∧ b = x1) ∨ (a = x2 ∧ b = x3) ∨ (a = x3 ∧ b = x2) := by rcases ha_cases with rfl | rfl | rfl <;> rcases hb_cases with rfl | rfl | rfl <;> try { contradiction } <;> tauto rcases hcases with ⟨ha, hb⟩ | ⟨ha, hb⟩ | ⟨ha, hb⟩ | ⟨ha, hb⟩ | ⟨ha, hb⟩ | ⟨ha, hb⟩ · left have : (⟨{a, b}, Finset.card_pair hab⟩ : {s : Finset V // s.card = 2}) = e1 := by apply Subtype.ext; change ({a, b} : Finset V) = {x1, x2}; rw [ha, hb] rw [this]; exact he1_D · left have : (⟨{a, b}, Finset.card_pair hab⟩ : {s : Finset V // s.card = 2}) = e1 := by apply Subtype.ext; change ({a, b} : Finset V) = {x1, x2}; rw [ha, hb, Finset.pair_comm] rw [this]; exact he1_D · left have : (⟨{a, b}, Finset.card_pair hab⟩ : {s : Finset V // s.card = 2}) = e2 := by apply Subtype.ext; change ({a, b} : Finset V) = {x1, x3}; rw [ha, hb] rw [this]; exact he2_D · left have : (⟨{a, b}, Finset.card_pair hab⟩ : {s : Finset V // s.card = 2}) = e2 := by apply Subtype.ext; change ({a, b} : Finset V) = {x1, x3}; rw [ha, hb, Finset.pair_comm] rw [this]; exact he2_D · right refine ⟨e1, he1_D, x1, x3, hx13_Gadj, ?_⟩ change symmDiff ({x1, x2} : Finset V) {a, b} = {x1, x3} rw [ha, hb, Finset.pair_comm x1 x2] have := two_token_domination_number_odd_p3_matching_le_symmDiff_pair_pair x2 x3 x1 hx32_ne.symm hx12_ne.symm hx13_ne.symm rw [this, Finset.pair_comm x3 x1] · right refine ⟨e1, he1_D, x1, x3, hx13_Gadj, ?_⟩ change symmDiff ({x1, x2} : Finset V) {a, b} = {x1, x3} rw [ha, hb, Finset.pair_comm x1 x2, Finset.pair_comm x3 x2] have := two_token_domination_number_odd_p3_matching_le_symmDiff_pair_pair x2 x3 x1 hx32_ne.symm hx12_ne.symm hx13_ne.symm rw [this, Finset.pair_comm x3 x1]
The domination number of F₂(G) is at most (|V| + 1) / 2.
By definition, the domination number of F₂(G) is the infimum of the sizes of all dominating sets. Since D is a dominating set of size (|V| + 1) / 2, the domination number is at most |D|.
uses
Nat.sInf_leunfold simple_graph_domination_number rw [← hD_total] exact Nat.sInf_le ⟨D, hdom, rfl⟩
two_token_domination_number_odd_p3_matching_le_symmDiff_pair_pair- The symmetric difference of two pairs with one shared element {a, x} and {a, b} equals {b, x}.
Finset.mem_symmDiff- An element belongs to the symmetric difference of two sets if and only if it belongs to one but not the other.
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 {a} if and only if it equals a.
SimpleGraph.card_neighborFinset_eq_degree- The number of neighbors of a vertex equals its degree in the graph.
Finset.card_eq_one.mp- A finite set has cardinality 1 if and only if it is a singleton set.
SimpleGraph.mem_neighborFinset- A vertex w belongs to the neighbor finset of v if and only if v and w are adjacent.
dif_neg- A dependent if-then-else evaluates to its second branch when the condition is false.
Classical.choose_spec- The element chosen by Classical.choose satisfies the existence property.
Finset.card_eq_two.mp- A finite set has cardinality 2 if and only if it consists of two distinct elements.
SimpleGraph.ne_of_adj- Adjacent vertices in a simple graph are distinct.
Finset.mem_filter- An element belongs to Finset.filter p s if and only if it belongs to s and satisfies predicate p.
Finset.mem_univ- Every element of a finite type belongs to Finset.univ.
Finset.card_pair- The set {a, b} has cardinality 2 whenever a ≠ b.
dif_pos- A dependent if-then-else evaluates to its first branch when the condition is true.
Subtype.ext- Two subtype elements are equal if their underlying values are equal.
Finset.pair_comm- Unordered pairs are commutative: {a, b} = {b, a}.
Finset.card_eq_sum_card_fiberwise- The size of a finite set s equals the sum over t of the sizes of the fibers f⁻¹(b) ∩ s.
Finset.sum_congr- Two sums are equal if their index sets match and their terms agree at every element.
Finset.sum_const- The sum of a constant value over a finite set equals the size of the set times the constant.
Nat.mul_div_cancel- Multiplying by n and then dividing by n returns the original number for any positive n.
Finset.card_insert_of_notMem- Inserting an element not already in a finite set increases its size by 1.
Finset.card_singleton- A singleton set has size 1.
Finset.card_sdiff_of_subset- The cardinality of t \ s for s ⊆ t is |t| - |s|.
Finset.subset_univ- Every finite set of vertices is a subset of the universal finset.
Finset.card_univ- The cardinality of the universal finset of α equals Fintype.card α.
Finset.card_le_card- If s ⊆ t, then |s| ≤ |t|.
Nat.sInf_le- The infimum of a set of natural numbers is at most any element of that set.
- The integer division identity 2 + (|V| - 3) / 2 = (|V| + 1) / 2 for |V| ≥ 3 is discharged automatically by omega.
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_domination_number_odd_p3_matching_le_symmDiff_pair_pair {V : Type*} [DecidableEq V] (a b x : V) (hab : a ≠ b) (hax : a ≠ x) (hbx : b ≠ x) : symmDiff ({a, x} : Finset V) {a, b} = {b, x} := by ext c rw [Finset.mem_symmDiff] simp only [Finset.mem_insert, Finset.mem_singleton] by_cases hca : c = a · subst hca simp [hab, hax] · by_cases hcx : c = x · subst hcx simp [hbx.symm, hax.symm] · by_cases hcb : c = b · subst hcb simp [hab.symm, hbx] · simp [hca, hcx, hcb]open scoped Classical in/-- If the complement of G has a vertex of degree 2 and all others degree 1 (isomorphic to P_3 union disjoint edges), then the domination number of F_2(G) is at most (n + 1) / 2. -/theorem two_token_domination_number_odd_p3_matching_le {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (hdeg : ∃ 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 classical obtain ⟨x2, hx2_deg, hothers⟩ := hdeg have hex : ∀ u, u ≠ x2 → ∃! w, Gᶜ.Adj u w := by intro u hu have h1 : (Gᶜ.neighborFinset u).card = 1 := by rw [SimpleGraph.card_neighborFinset_eq_degree, hothers u hu] obtain ⟨w, hw⟩ := Finset.card_eq_one.mp h1 refine ⟨w, ?_, ?_⟩ · have : w ∈ Gᶜ.neighborFinset u := by rw [hw]; simp exact (SimpleGraph.mem_neighborFinset _ _ _).mp this · intro y hy have : y ∈ Gᶜ.neighborFinset u := (SimpleGraph.mem_neighborFinset _ _ _).mpr hy rw [hw] at this simpa using this let p : V → V := fun v => if h : v = x2 then x2 else Classical.choose (hex v h) have hp_def : ∀ v (hv : v ≠ x2), p v = Classical.choose (hex v hv) := by intro v hv dsimp [p] rw [dif_neg hv] have hp_adj : ∀ v (hv : v ≠ x2), Gᶜ.Adj v (p v) := by intro v hv rw [hp_def v hv] exact (Classical.choose_spec (hex v hv)).1 have hp_uniq : ∀ v (hv : v ≠ x2) w, Gᶜ.Adj v w → w = p v := by intro v hv w hw rw [hp_def v hv] exact (Classical.choose_spec (hex v hv)).2 w hw have h2 : (Gᶜ.neighborFinset x2).card = 2 := by rw [SimpleGraph.card_neighborFinset_eq_degree, hx2_deg] obtain ⟨x1, x3, hx13_ne, hx2_nbrs⟩ := Finset.card_eq_two.mp h2 have hx1_mem : x1 ∈ Gᶜ.neighborFinset x2 := by rw [hx2_nbrs]; simp have hx3_mem : x3 ∈ Gᶜ.neighborFinset x2 := by rw [hx2_nbrs]; simp have hx21_adj : Gᶜ.Adj x2 x1 := (SimpleGraph.mem_neighborFinset _ _ _).mp hx1_mem have hx23_adj : Gᶜ.Adj x2 x3 := (SimpleGraph.mem_neighborFinset _ _ _).mp hx3_mem have hx12_ne : x1 ≠ x2 := ((Gᶜ).ne_of_adj hx21_adj).symm have hx32_ne : x3 ≠ x2 := ((Gᶜ).ne_of_adj hx23_adj).symm have hpx1 : p x1 = x2 := (hp_uniq x1 hx12_ne x2 hx21_adj.symm).symm have hpx3 : p x3 = x2 := (hp_uniq x3 hx32_ne x2 hx23_adj.symm).symm let W : Finset V := Finset.univ.filter (fun v => v ≠ x1 ∧ v ≠ x2 ∧ v ≠ x3) have hpW : ∀ u ∈ W, p u ∈ W := by intro u hu rw [Finset.mem_filter] at hu ⊢ obtain ⟨-, hu1, hu2, hu3⟩ := hu have hpadj := hp_adj u hu2 refine ⟨Finset.mem_univ _, ?_, ?_, ?_⟩ · intro h have h1 : Gᶜ.Adj x1 u := by rw [h] at hpadj; exact hpadj.symm have := hp_uniq x1 hx12_ne u h1 rw [hpx1] at this exact hu2 this · intro h have h2 : Gᶜ.Adj x2 u := by rw [h] at hpadj; exact hpadj.symm have hmem : u ∈ Gᶜ.neighborFinset x2 := (SimpleGraph.mem_neighborFinset _ _ _).mpr h2 rw [hx2_nbrs] at hmem simp only [Finset.mem_insert, Finset.mem_singleton] at hmem rcases hmem with rfl | rfl · exact hu1 rfl · exact hu3 rfl · intro h have h3 : Gᶜ.Adj x3 u := by rw [h] at hpadj; exact hpadj.symm have := hp_uniq x3 hx32_ne u h3 rw [hpx3] at this exact hu2 this have hpinvol : ∀ u ∈ W, p (p u) = u := by intro u hu have hpuW := hpW u hu rw [Finset.mem_filter] at hu hpuW have hadj := (hp_adj u hu.2.2.1).symm exact (hp_uniq (p u) hpuW.2.2.1 u hadj).symm have hpne : ∀ u ∈ W, p u ≠ u := by intro u hu rw [Finset.mem_filter] at hu intro h exact (Gᶜ).ne_of_adj (hp_adj u hu.2.2.1) h.symm have hGadj : ∀ u v : V, u ≠ v → ¬ Gᶜ.Adj u v → G.Adj u v := by intro u v huv hc by_contra h exact hc ⟨huv, h⟩ have hx13_Gadj : G.Adj x1 x3 := by apply hGadj x1 x3 hx13_ne intro hc have := hp_uniq x1 hx12_ne x3 hc rw [hpx1] at this exact hx32_ne this let f : V → {s : Finset V // s.card = 2} := fun u => if h : u ∈ W then ⟨{u, p u}, Finset.card_pair (hpne u h).symm⟩ else ⟨{x1, x2}, Finset.card_pair hx12_ne⟩ have hfib : ∀ u ∈ W, (W.filter (fun v => f v = f u)) = ({u, p u} : Finset V) := by intro u hu ext v simp only [Finset.mem_filter, Finset.mem_insert, Finset.mem_singleton] constructor · rintro ⟨hvW, heq⟩ have huW := hu dsimp [f] at heq rw [dif_pos hvW, dif_pos huW] at heq have hmem : v ∈ (⟨{v, p v}, Finset.card_pair (hpne v hvW).symm⟩ : {s : Finset V // s.card = 2}).val := by simp rw [heq] at hmem simpa using hmem · rintro (rfl | rfl) · exact ⟨hu, rfl⟩ · refine ⟨hpW u hu, ?_⟩ dsimp [f] rw [dif_pos (hpW u hu), dif_pos hu] apply Subtype.ext change ({p u, p (p u)} : Finset V) = {u, p u} rw [hpinvol u hu, Finset.pair_comm] let DW : Finset {s : Finset V // s.card = 2} := W.image f have hmaps : Set.MapsTo f (↑W) (↑DW) := by intro x hx exact Finset.mem_image.mpr ⟨x, hx, rfl⟩ have hsum := Finset.card_eq_sum_card_fiberwise hmaps have hfiber2 : ∀ b ∈ DW, (W.filter (fun a => f a = b)).card = 2 := by intro b hb obtain ⟨u, hu, rfl⟩ := Finset.mem_image.mp hb rw [hfib u hu, Finset.card_pair (hpne u hu).symm] have h1 : W.card = DW.card * 2 := by rw [hsum, Finset.sum_congr rfl hfiber2] simp [Finset.sum_const] have hDWcard : DW.card = W.card / 2 := by rw [h1, Nat.mul_div_cancel _ (by norm_num : 0 < 2)] have hx23 : x2 ∉ ({x3} : Finset V) := by simp [hx32_ne.symm] have hx123 : x1 ∉ ({x2, x3} : Finset V) := by simp [hx12_ne, hx13_ne] have hcardX : ({x1, x2, x3} : Finset V).card = 3 := by rw [Finset.card_insert_of_notMem hx123, Finset.card_insert_of_notMem hx23, Finset.card_singleton] have hW_compl : W = Finset.univ \ {x1, x2, x3} := by ext v simp [W] have hWcard : W.card = Fintype.card V - 3 := by rw [hW_compl, Finset.card_sdiff_of_subset (Finset.subset_univ _), Finset.card_univ, hcardX] have hV3 : 3 ≤ Fintype.card V := by rw [← Finset.card_univ, ← hcardX] exact Finset.card_le_card (Finset.subset_univ _) let e1 : {s : Finset V // s.card = 2} := ⟨{x1, x2}, Finset.card_pair hx12_ne⟩ let e2 : {s : Finset V // s.card = 2} := ⟨{x1, x3}, Finset.card_pair hx13_ne⟩ have he1_not_DW : e1 ∉ DW := by intro hmem obtain ⟨u, huW, heq⟩ := Finset.mem_image.mp hmem have huW_prop : u ∈ W := huW dsimp [f] at heq rw [dif_pos huW] at heq have hval : ({u, p u} : Finset V) = {x1, x2} := Subtype.ext_iff.mp heq have hx1 : x1 ∈ ({u, p u} : Finset V) := by rw [hval]; simp simp only [Finset.mem_insert, Finset.mem_singleton] at hx1 rw [Finset.mem_filter] at huW_prop rcases hx1 with rfl | hpu · exact huW_prop.2.1 rfl · have hpuW := hpW u huW rw [Finset.mem_filter] at hpuW exact hpuW.2.1 hpu.symm have he2_not_DW : e2 ∉ DW := by intro hmem obtain ⟨u, huW, heq⟩ := Finset.mem_image.mp hmem have huW_prop : u ∈ W := huW dsimp [f] at heq rw [dif_pos huW] at heq have hval : ({u, p u} : Finset V) = {x1, x3} := Subtype.ext_iff.mp heq have hx1 : x1 ∈ ({u, p u} : Finset V) := by rw [hval]; simp simp only [Finset.mem_insert, Finset.mem_singleton] at hx1 rw [Finset.mem_filter] at huW_prop rcases hx1 with rfl | hpu · exact huW_prop.2.1 rfl · have hpuW := hpW u huW rw [Finset.mem_filter] at hpuW exact hpuW.2.1 hpu.symm have he12_ne : e1 ≠ e2 := by intro h have hval : e1.val = e2.val := by rw [h] change ({x1, x2} : Finset V) = {x1, x3} at hval have hx2 : x2 ∈ ({x1, x3} : Finset V) := by rw [← hval]; simp simp only [Finset.mem_insert, Finset.mem_singleton] at hx2 rcases hx2 with rfl | rfl · exact hx12_ne.symm rfl · exact hx32_ne.symm rfl let D : Finset {s : Finset V // s.card = 2} := insert e1 (insert e2 DW) have he1_not : e1 ∉ insert e2 DW := by simp [he12_ne, he1_not_DW] have hDcard : D.card = 2 + DW.card := by dsimp [D] rw [Finset.card_insert_of_notMem he1_not, Finset.card_insert_of_notMem he2_not_DW] omega have hD_total : D.card = (Fintype.card V + 1) / 2 := by rw [hDcard, hDWcard, hWcard] omega have hdom_u : ∀ a b : V, (hab : a ≠ b) → a ∈ W → (⟨{a, b}, Finset.card_pair hab⟩ : {s : Finset V // s.card = 2}) ∈ D ∨ ∃ t ∈ D, (token_graph G 2).Adj t ⟨{a, b}, Finset.card_pair hab⟩ := by intro a b hab haW have hfa_DW : f a ∈ DW := Finset.mem_image.mpr ⟨a, haW, rfl⟩ have hfa_D : f a ∈ D := by simp [D, hfa_DW] have hfa_val : (f a).val = {a, p a} := by dsimp [f] rw [dif_pos haW] by_cases hb : b = p a · left subst hb have heq : (⟨{a, p a}, Finset.card_pair hab⟩ : {s : Finset V // s.card = 2}) = f a := by apply Subtype.ext rw [hfa_val] rw [heq] exact hfa_D · right refine ⟨f a, hfa_D, b, p a, ?_, ?_⟩ · apply hGadj · exact hb · intro hc have hpadj : Gᶜ.Adj (p a) b := hc.symm have hpaW := hpW a haW rw [Finset.mem_filter] at hpaW have huniq := hp_uniq (p a) hpaW.2.2.1 b hpadj rw [hpinvol a haW] at huniq exact hab huniq.symm · rw [hfa_val] change symmDiff ({a, p a} : Finset V) {a, b} = {b, p a} have hpa_ne_a : a ≠ p a := (hpne a haW).symm exact two_token_domination_number_odd_p3_matching_le_symmDiff_pair_pair a b (p a) hab hpa_ne_a hb have he1_D : e1 ∈ D := by simp [D] have he2_D : e2 ∈ D := by simp [D] 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 haW : a ∈ W · exact hdom_u a b hab haW · by_cases hbW : b ∈ W · have hsymm := hdom_u b a hab.symm hbW have hpair_eq : (⟨{b, a}, Finset.card_pair hab.symm⟩ : {s : Finset V // s.card = 2}) = ⟨{a, b}, Finset.card_pair hab⟩ := by apply Subtype.ext exact Finset.pair_comm b a rw [hpair_eq] at hsymm exact hsymm · have ha_cases : a = x1 ∨ a = x2 ∨ a = x3 := by simp only [W, Finset.mem_filter, Finset.mem_univ, true_and, not_and] at haW tauto have hb_cases : b = x1 ∨ b = x2 ∨ b = x3 := by simp only [W, Finset.mem_filter, Finset.mem_univ, true_and, not_and] at hbW tauto have hcases : (a = x1 ∧ b = x2) ∨ (a = x2 ∧ b = x1) ∨ (a = x1 ∧ b = x3) ∨ (a = x3 ∧ b = x1) ∨ (a = x2 ∧ b = x3) ∨ (a = x3 ∧ b = x2) := by rcases ha_cases with rfl | rfl | rfl <;> rcases hb_cases with rfl | rfl | rfl <;> try { contradiction } <;> tauto rcases hcases with ⟨ha, hb⟩ | ⟨ha, hb⟩ | ⟨ha, hb⟩ | ⟨ha, hb⟩ | ⟨ha, hb⟩ | ⟨ha, hb⟩ · left have : (⟨{a, b}, Finset.card_pair hab⟩ : {s : Finset V // s.card = 2}) = e1 := by apply Subtype.ext; change ({a, b} : Finset V) = {x1, x2}; rw [ha, hb] rw [this]; exact he1_D · left have : (⟨{a, b}, Finset.card_pair hab⟩ : {s : Finset V // s.card = 2}) = e1 := by apply Subtype.ext; change ({a, b} : Finset V) = {x1, x2}; rw [ha, hb, Finset.pair_comm] rw [this]; exact he1_D · left have : (⟨{a, b}, Finset.card_pair hab⟩ : {s : Finset V // s.card = 2}) = e2 := by apply Subtype.ext; change ({a, b} : Finset V) = {x1, x3}; rw [ha, hb] rw [this]; exact he2_D · left have : (⟨{a, b}, Finset.card_pair hab⟩ : {s : Finset V // s.card = 2}) = e2 := by apply Subtype.ext; change ({a, b} : Finset V) = {x1, x3}; rw [ha, hb, Finset.pair_comm] rw [this]; exact he2_D · right refine ⟨e1, he1_D, x1, x3, hx13_Gadj, ?_⟩ change symmDiff ({x1, x2} : Finset V) {a, b} = {x1, x3} rw [ha, hb, Finset.pair_comm x1 x2] have := two_token_domination_number_odd_p3_matching_le_symmDiff_pair_pair x2 x3 x1 hx32_ne.symm hx12_ne.symm hx13_ne.symm rw [this, Finset.pair_comm x3 x1] · right refine ⟨e1, he1_D, x1, x3, hx13_Gadj, ?_⟩ change symmDiff ({x1, x2} : Finset V) {a, b} = {x1, x3} rw [ha, hb, Finset.pair_comm x1 x2, Finset.pair_comm x3 x2] have := two_token_domination_number_odd_p3_matching_le_symmDiff_pair_pair x2 x3 x1 hx32_ne.symm hx12_ne.symm hx13_ne.symm rw [this, Finset.pair_comm x3 x1] unfold simple_graph_domination_number rw [← hD_total] exact Nat.sInf_le ⟨D, hdom, rfl⟩