two_token_dominating_set_card_ge_ceil_half
Let G be a finite simple graph on vertex type V with domination number at least 2. Then every dominating set D of the 2-token graph F_2(G) satisfies (Fintype.card V + 1) / 2 ≤ D.card.
Statement
theorem two_token_dominating_set_card_ge_ceil_half {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (hγ : 2 ≤ simple_graph_domination_number G) (D : Finset { s : Finset V // s.card = 2 }) (hD : simple_graph_is_dominating (token_graph G 2) (D : Set { s : Finset V // s.card = 2 })) : (Fintype.card V + 1) / 2 ≤ D.card
- Source
- arXiv:2611.15124, Theorem 1.3
- Verified
- 14 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- 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.
- 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_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_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)…
Read back from the Lean
For any finite type $V$ with decidable equality, any simple graph $G$ on $V$, if the domination number of $G$ is at least 2, and $D$ is a finite set of 2-element subsets of $V$ that forms a dominating set in the 2-token graph of $G$ (where two 2-element subsets are adjacent if their symmetric difference consists of two adjacent vertices in $G$), then the cardinality of $D$ is at least $\lceil |V| / 2 \rceil$ (formulated as (Fintype.card V + 1) / 2 ≤ D.card 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 shows that any dominating set D of the 2-token graph F_2(G) satisfies |V| ≤ 2 * |D|, which implies ⌈|V|/2⌉ ≤ |D|. Taking U to be the union of all 2-element sets in D, subadditivity gives |U| ≤ 2 * |D|, while the dominating property of D forces the complement V \ U to have at most one vertex. Assuming for contradiction that |V| > 2 * |D|, we must have |U| = 2 * |D| and V \ U = {w} for a single vertex w. Because the domination number γ(G) ≥ 2, w has a non-neighbor z ∈ U, which belongs to some token s = {z, z'} ∈ D. To dominate the pair {w, z'}, D must contain another token t = {z', b'} sharing the vertex z'. This overlap between s and t reduces the size of U to at most 3 + 2 * (|D| - 2) = 2 * |D| - 1, contradicting |U| = 2 * |D|.
Define U as the union of all 2-element subsets in D, and observe that every s ∈ D is contained in U.
The set U is defined as ⋃_{s ∈ D} s. For any s ∈ D and any vertex v ∈ s, v belongs to U by definition of the union over D (Finset.mem_biUnion.mpr).
uses
Finset.mem_biUnion.mprclassical set U : Finset V := D.biUnion (fun s => s.val) with hUdef have hsubU : ∀ s ∈ D, s.val ⊆ U := by intro s hs v hv rw [hUdef] exact Finset.mem_biUnion.mpr ⟨s, hs, hv⟩
The cardinality of U is at most 2 * |D|.
By subadditivity of the union (Finset.card_biUnion_le), |U| ≤ ∑_{s ∈ D} |s|. Since every token s ∈ D has size 2 (Finset.sum_congr), this sum equals ∑_{s ∈ D} 2 = 2 * |D| (Finset.sum_const, mul_comm).
uses
Finset.card_biUnion_le,Finset.sum_congr,Finset.sum_const,mul_commhave hUle : U.card ≤ 2 * D.card := by calc U.card ≤ ∑ s ∈ D, (s.val).card := Finset.card_biUnion_le _ = ∑ _s ∈ D, 2 := by apply Finset.sum_congr rfl intro s _ exact s.property _ = 2 * D.card := by simp [Finset.sum_const, mul_comm]
The complement V \ U contains at most one vertex.
To show |V \ U| ≤ 1, suppose for contradiction that there exist distinct vertices x ≠ y in V \ U. The pair {x, y} has size 2 and cannot belong to D because neither x nor y is in U. Since D dominates the 2-token graph F_2(G), {x, y} must be adjacent to some token u ∈ D. By the definition of F_2(G), the symmetric difference u ∆ {x, y} equals {p, q} for some adjacent vertices p, q in G. But u ⊆ U while x, y ∉ U, so x, y and any element a ∈ u are three distinct vertices all belonging to u ∆ {x, y}. This contradicts the fact that {p, q} has cardinality 2.
uses
Finset.card_le_one,Finset.mem_sdiff.mp,Finset.card_pair,Finset.mem_biUnion.mpr,Finset.card_pos.mp,Finset.mem_symmDiff,Or.inr,Or.inl,Finset.mem_insert.mp,Finset.mem_singleton,Finset.card_insert_of_notMem,Finset.card_singleton,G.ne_of_adj,Finset.card_le_cardhave hcompl : (Finset.univ \ U).card ≤ 1 := by rw [Finset.card_le_one] intro x hx y hy by_contra hxy have hxU : x ∉ U := (Finset.mem_sdiff.mp hx).2 have hyU : y ∉ U := (Finset.mem_sdiff.mp hy).2 have hcard2 : ({x, y} : Finset V).card = 2 := Finset.card_pair hxy rcases hD (⟨{x,y}, hcard2⟩ : {s : Finset V // s.card = 2}) with hzD | ⟨u, huD, hadj⟩ · apply hxU rw [hUdef] exact Finset.mem_biUnion.mpr ⟨_, hzD, by simp⟩ · obtain ⟨p, q, hpq, hdiff⟩ := hadj have huU : ∀ v ∈ u.val, v ∈ U := hsubU u huD have hpos : 0 < u.val.card := by rw [u.property]; norm_num obtain ⟨a, ha⟩ := Finset.card_pos.mp hpos have haU : a ∈ U := huU a ha have hax : a ≠ x := fun h => hxU (h ▸ haU) have hay : a ≠ y := fun h => hyU (h ▸ haU) have hdiff' : symmDiff u.val ({x, y} : Finset V) = {p, q} := hdiff have hxS : x ∈ symmDiff u.val ({x, y} : Finset V) := by rw [Finset.mem_symmDiff] exact Or.inr ⟨by simp, fun hxmem => hxU (huU x hxmem)⟩ have hyS : y ∈ symmDiff u.val ({x, y} : Finset V) := by rw [Finset.mem_symmDiff] exact Or.inr ⟨by simp, fun hymem => hyU (huU y hymem)⟩ have haS : a ∈ symmDiff u.val ({x, y} : Finset V) := by rw [Finset.mem_symmDiff] refine Or.inl ⟨ha, ?_⟩ intro hav rcases Finset.mem_insert.mp hav with h | h · exact hax h · rw [Finset.mem_singleton] at h exact hay h have hsub : ({a, x, y} : Finset V) ⊆ ({p, q} : Finset V) := by intro v hv rw [← hdiff'] rcases Finset.mem_insert.mp hv with rfl | hv · exact haS rcases Finset.mem_insert.mp hv with rfl | hv · exact hxS · rw [Finset.mem_singleton] at hv subst hv exact hyS have h3 : ({a, x, y} : Finset V).card = 3 := by rw [Finset.card_insert_of_notMem (by simp [hax, hay]), Finset.card_insert_of_notMem (by simp [hxy]), Finset.card_singleton] have h2 : ({p, q} : Finset V).card = 2 := Finset.card_pair (G.ne_of_adj hpq) have := Finset.card_le_card hsub omega
The total number of vertices partitions as |V| = |U| + |V \ U|, and to prove the theorem it suffices to show |V| ≤ 2 * |D|.
Since U ⊆ V, the vertices partition into U and V \ U, so |V| = |U| + |V \ U| (Finset.card_sdiff_add_card_eq_card, Finset.subset_univ, Finset.card_univ). If |V| ≤ 2 * |D|, then (|V| + 1) / 2 ≤ (2 * |D| + 1) / 2 = |D|, which yields the theorem via integer arithmetic.
uses
Finset.card_sdiff_add_card_eq_card,Finset.subset_univ,Finset.card_univhave hsplit : Fintype.card V = U.card + (Finset.univ \ U).card := by have h := Finset.card_sdiff_add_card_eq_card (Finset.subset_univ U) rw [Finset.card_univ] at h omega suffices hmain : Fintype.card V ≤ 2 * D.card by omega
Assuming for contradiction that |V| > 2 * |D|, we have |V| = 2 * |D| + 1, |U| = 2 * |D|, and V \ U consists of a single unique vertex w.
Suppose |V| > 2 * |D|. Combining |V| = |U| + |V \ U| with |U| ≤ 2 * |D| and |V \ U| ≤ 1 leaves only |V| = 2 * |D| + 1, |U| = 2 * |D|, and |V \ U| = 1. Since |V \ U| = 1, there is an element w ∈ V \ U (Finset.card_pos.mp, Finset.mem_sdiff.mp), and any other element of V \ U must equal w (Finset.card_le_one.mp).
uses
Finset.card_pos.mp,Finset.mem_sdiff.mp,Finset.card_le_one.mpby_contra hlt have hn : Fintype.card V = 2 * D.card + 1 := by omega have hUeq : U.card = 2 * D.card := by omega have hcompeq : (Finset.univ \ U).card = 1 := by omega have hWpos : 0 < (Finset.univ \ U).card := by omega obtain ⟨w, hw⟩ := Finset.card_pos.mp hWpos have hwU : w ∉ U := (Finset.mem_sdiff.mp hw).2 have hWuniq : ∀ x ∈ Finset.univ \ U, x = w := by have h := Finset.card_le_one.mp hcompl exact fun x hx => h x hx w hw
There exists a vertex z ≠ w that is not adjacent to w in G.
If every vertex other than w were adjacent to w, the singleton {w} would dominate G, meaning G would have domination number at most 1 (Nat.sInf_le). This contradicts the assumption that γ(G) ≥ 2. Thus, a non-neighbor z ≠ w must exist.
uses
Nat.sInf_lehave hznondom : ∃ z : V, z ≠ w ∧ ¬ G.Adj w z := by by_contra h push Not at h have hdom : simple_graph_is_dominating G (({w} : Finset V) : Set V) := by intro v by_cases hv : v = w · left; simp [hv] · right; exact ⟨w, by simp, h v hv⟩ have hmem : 1 ∈ {k : ℕ | ∃ S : Finset V, simple_graph_is_dominating G (S : Set V) ∧ S.card = k} := ⟨{w}, hdom, by simp⟩ have hle : simple_graph_domination_number G ≤ 1 := Nat.sInf_le hmem omega obtain ⟨z, hzw, hzw'⟩ := hznondom
The vertex z belongs to U, so z is in some token s ∈ D of the form s = {z, z'} with z' ≠ z and z' ≠ w.
Since z ≠ w and w is the only vertex outside U, z must lie in U (Finset.mem_sdiff.mpr, Finset.mem_univ). By definition of U, z belongs to some s ∈ D (Finset.mem_biUnion.mp). Removing z from s leaves a singleton {z'} (Finset.card_erase_of_mem, Finset.card_eq_one.mp), so s = {z, z'} with z' ≠ z (Finset.insert_erase). Because z' ∈ s ⊆ U while w ∉ U, we also have w ≠ z'.
uses
Finset.mem_sdiff.mpr,Finset.mem_univ,Finset.mem_biUnion.mp,Finset.card_erase_of_mem,Finset.card_eq_one.mp,Finset.mem_singleton_self,Finset.mem_erase.mp,Finset.insert_erasehave hzU : z ∈ U := by by_contra hz have : z ∈ Finset.univ \ U := Finset.mem_sdiff.mpr ⟨Finset.mem_univ z, hz⟩ exact hzw (hWuniq z this) obtain ⟨s, hsD, hzs⟩ := Finset.mem_biUnion.mp hzU have hsval : s.val ⊆ U := hsubU s hsD have hscard : (s.val.erase z).card = 1 := by rw [Finset.card_erase_of_mem hzs, s.property] obtain ⟨z', hz'E⟩ := Finset.card_eq_one.mp hscard have hz'erase : z' ∈ s.val.erase z := by rw [hz'E]; exact Finset.mem_singleton_self z' have hz'ne : z' ≠ z := (Finset.mem_erase.mp hz'erase).1 have hz'mem : z' ∈ s.val := (Finset.mem_erase.mp hz'erase).2 have hs_eq : s.val = {z, z'} := by conv_lhs => rw [← Finset.insert_erase hzs] rw [hz'E] have hz'U : z' ∈ U := hsval hz'mem have hwz' : w ≠ z' := fun h => hwU (h ▸ hz'U)
The pair y = {w, z'} is a vertex of F_2(G) not in D, and is dominated by some token t ∈ D adjacent to y.
Because w ≠ z', the pair y = {w, z'} has size 2 (Finset.card_pair). It cannot belong to D because w ∈ y but w ∉ U (Finset.mem_biUnion.mpr). Because D dominates F_2(G), y must be adjacent in F_2(G) to some token t ∈ D.
uses
Finset.card_pair,Finset.mem_biUnion.mprset y : { s : Finset V // s.card = 2 } := ⟨{w, z'}, Finset.card_pair hwz'⟩ with hydef have hyval : y.val = ({w, z'} : Finset V) := rfl have hynd : y ∉ D := by intro hy apply hwU rw [hUdef] exact Finset.mem_biUnion.mpr ⟨y, hy, by rw [hyval]; simp⟩ have hdomy : ∃ t ∈ D, (token_graph G 2).Adj t y := by rcases hD y with hy | ⟨t, htD, hadj⟩ · exact absurd hy hynd · exact ⟨t, htD, hadj⟩ obtain ⟨t, htD, hadj⟩ := hdomy
The dominating token t ∈ D must contain z', and can be written as t = {z', b'} for some vertex b' ≠ z'.
By the definition of adjacency in F_2(G), the symmetric difference t ∆ y equals an edge {p, q} of G, which has size 2. Since t ⊆ U and w ∉ U, w ∉ t. If z' were not in t, then t and y = {w, z'} would be disjoint (Finset.disjoint_left), forcing |t ∆ y| = |t ∪ y| = 2 + 2 = 4 (Finset.symmDiff_eq_union, Finset.card_union_of_disjoint), a contradiction. Thus z' ∈ t. Removing z' from t leaves a singleton {b'} with b' ≠ z' (Finset.card_erase_of_mem, Finset.card_eq_one.mp), giving t = {z', b'} (Finset.insert_erase).
uses
Finset.disjoint_left,Finset.symmDiff_eq_union,Finset.card_union_of_disjoint,Finset.card_pair,G.ne_of_adj,Finset.card_erase_of_mem,Finset.card_eq_one.mp,Finset.mem_singleton_self,Finset.mem_erase.mp,Finset.insert_eraseobtain ⟨p, q, hpq, hdiff⟩ := hadj have htU : ∀ v ∈ t.val, v ∈ U := hsubU t htD have hwt : w ∉ t.val := fun h => hwU (htU w h) have hz't : z' ∈ t.val := by by_contra hz'nt have hdisj : Disjoint t.val y.val := by rw [Finset.disjoint_left] intro v hv hvy rw [hyval] at hvy rcases Finset.mem_insert.mp hvy with rfl | hvy · exact hwt hv · rw [Finset.mem_singleton] at hvy exact hz'nt (hvy ▸ hv) have hsym : symmDiff t.val y.val = t.val ∪ y.val := Finset.symmDiff_eq_union hdisj have hc4 : (t.val ∪ y.val).card = 4 := by rw [Finset.card_union_of_disjoint hdisj, t.property, hyval, Finset.card_pair hwz'] have hc2 : (symmDiff t.val y.val).card = 2 := by rw [hdiff]; exact Finset.card_pair (G.ne_of_adj hpq) rw [hsym] at hc2 omega have hterase : (t.val.erase z').card = 1 := by rw [Finset.card_erase_of_mem hz't, t.property] obtain ⟨b', hb'E⟩ := Finset.card_eq_one.mp hterase have hb'erase : b' ∈ t.val.erase z' := by rw [hb'E]; exact Finset.mem_singleton_self b' have hb'ne : b' ≠ z' := (Finset.mem_erase.mp hb'erase).1 have hb'mem : b' ∈ t.val := (Finset.mem_erase.mp hb'erase).2 have ht_eq : t.val = {z', b'} := by conv_lhs => rw [← Finset.insert_erase hz't] rw [hb'E]
The edge between t and y in F_2(G) is {w, b'}, so w is adjacent to b' in G, which implies b' ≠ z.
Since t = {z', b'} and y = {w, z'}, their symmetric difference contains w and b'. Since t ∆ y = {p, q} has size 2, it must be {w, b'} = {p, q} (Finset.eq_of_subset_of_card_le). Because p and q are adjacent in G, w is adjacent to b' (G.adj_comm). But z was chosen not to be adjacent to w, so b' cannot equal z.
uses
Finset.mem_symmDiff,Or.inr,Or.inl,Finset.mem_insert,Finset.mem_singleton,Finset.mem_insert.mp,Finset.eq_of_subset_of_card_le,Finset.card_pair,G.ne_of_adj,Finset.mem_insert_self,G.adj_commhave hwS : w ∈ symmDiff t.val y.val := by rw [Finset.mem_symmDiff] exact Or.inr ⟨by rw [hyval]; simp, hwt⟩ have hb'S : b' ∈ symmDiff t.val y.val := by rw [Finset.mem_symmDiff] refine Or.inl ⟨hb'mem, ?_⟩ rw [hyval] simp only [Finset.mem_insert, Finset.mem_singleton, not_or] exact ⟨fun h => hwU (h ▸ htU b' hb'mem), hb'ne⟩ have hwq : w ∈ ({p, q} : Finset V) := by rw [← hdiff]; exact hwS have hb'q : b' ∈ ({p, q} : Finset V) := by rw [← hdiff]; exact hb'S have hwb' : w ≠ b' := fun h => hwU (h ▸ htU b' hb'mem) have hsubpq : ({w, b'} : Finset V) ⊆ ({p, q} : Finset V) := by intro v hv rcases Finset.mem_insert.mp hv with rfl | hv · exact hwq · rw [Finset.mem_singleton] at hv subst hv exact hb'q have heq : ({w, b'} : Finset V) = {p, q} := by apply Finset.eq_of_subset_of_card_le hsubpq rw [Finset.card_pair (G.ne_of_adj hpq), Finset.card_pair hwb'] have hwadj : G.Adj w b' := by have hp : p ∈ ({w, b'} : Finset V) := by rw [heq]; exact Finset.mem_insert_self p {q} have hq : q ∈ ({w, b'} : Finset V) := by rw [heq]; simp rw [Finset.mem_insert, Finset.mem_singleton] at hp hq rcases hp with hp | hp <;> rcases hq with hq | hq · exact absurd (hp.trans hq.symm) (G.ne_of_adj hpq) · rw [hp, hq] at hpq; exact hpq · rw [hp, hq] at hpq; exact (G.adj_comm b' w).mp hpq · exact absurd (hp.trans hq.symm) (G.ne_of_adj hpq) by_cases hbz : b' = z · exact hzw' (hbz ▸ hwadj) · have hst : s ≠ t := by
The tokens s and t are distinct elements of D, and U is covered by {z, z', b'} ∪ ⋃_{u ∈ D \ {s, t}} u, giving |U| ≤ 3 + 2 * |D \ {s, t}|.
Since s = {z, z'} and t = {z', b'} with b' ≠ z and z' ≠ z, s and t are distinct tokens in D. Every element of U belongs to s, to t, or to some other token in D \ {s, t}, so U ⊆ (s ∪ t) ∪ ⋃_{u ∈ D \ {s, t}} u = {z, z', b'} ∪ ⋃_{u ∈ D \ {s, t}} u. Since |{z, z', b'}| ≤ 3 and each of the remaining tokens in D \ {s, t} has size 2, the union has cardinality at most 3 + 2 * |(D \ {s}) \ {t}| (Finset.card_union_le, Finset.card_biUnion_le, Finset.sum_const).
uses
Finset.mem_insert.mp,Finset.mem_singleton,Finset.mem_biUnion.mp,Finset.mem_union,Finset.mem_insert,Finset.mem_biUnion.mpr,Finset.mem_erase.mpr,Finset.card_le_card,Finset.card_union_le,Finset.card_insert_le,Finset.card_singleton,Finset.card_biUnion_le,Finset.sum_congr,Finset.sum_const,mul_commintro hst_eq have hzt : z ∈ t.val := by rw [← hst_eq]; exact hzs rw [ht_eq] at hzt rcases Finset.mem_insert.mp hzt with h | h · exact hz'ne h.symm · rw [Finset.mem_singleton] at h exact hbz h.symm have hcover : U ⊆ ({z, z', b'} : Finset V) ∪ ((D.erase s).erase t).biUnion (fun u => u.val) := by intro v hv rw [hUdef] at hv obtain ⟨u, huD, hvu⟩ := Finset.mem_biUnion.mp hv rw [Finset.mem_union] by_cases hus : u = s · left rw [hus, hs_eq] at hvu simp only [Finset.mem_insert, Finset.mem_singleton] at hvu ⊢ tauto · by_cases hut : u = t · left rw [hut, ht_eq] at hvu simp only [Finset.mem_insert, Finset.mem_singleton] at hvu ⊢ tauto · right exact Finset.mem_biUnion.mpr ⟨u, Finset.mem_erase.mpr ⟨hut, Finset.mem_erase.mpr ⟨hus, huD⟩⟩, hvu⟩ have hcard_cover : U.card ≤ 3 + 2 * ((D.erase s).erase t).card := by have h1 : U.card ≤ (({z, z', b'} : Finset V) ∪ ((D.erase s).erase t).biUnion (fun u => u.val)).card := Finset.card_le_card hcover have h2 : (({z, z', b'} : Finset V) ∪ ((D.erase s).erase t).biUnion (fun u => u.val)).card ≤ ({z, z', b'} : Finset V).card + (((D.erase s).erase t).biUnion (fun u => u.val)).card := Finset.card_union_le _ _ have h3 : ({z, z', b'} : Finset V).card ≤ 3 := by have ha1 := Finset.card_insert_le z ({z', b'} : Finset V) have ha2 := Finset.card_insert_le z' ({b'} : Finset V) simp only [Finset.card_singleton] at ha1 ha2 omega have h4 : (((D.erase s).erase t).biUnion (fun u => u.val)).card ≤ 2 * ((D.erase s).erase t).card := by calc _ ≤ ∑ u ∈ (D.erase s).erase t, (u.val).card := Finset.card_biUnion_le _ = ∑ _u ∈ (D.erase s).erase t, 2 := by apply Finset.sum_congr rfl intro u _ exact u.property _ = 2 * ((D.erase s).erase t).card := by simp [Finset.sum_const, mul_comm] omega
The cardinality of D \ {s, t} is |D| - 2, which yields |U| ≤ 2 * |D| - 1 < 2 * |D|, contradicting |U| = 2 * |D|.
Since s and t are distinct elements of D, |D| ≥ |{s, t}| = 2 (Finset.card_pair, Finset.card_le_card), and removing both yields |(D \ {s}) \ {t}| = |D| - 2 (Finset.card_erase_of_mem). Substituting this into the previous bound gives |U| ≤ 3 + 2 * (|D| - 2) = 2 * |D| - 1. But this contradicts |U| = 2 * |D|, closing the contradiction and finishing the proof.
uses
Finset.mem_erase.mpr,Finset.card_erase_of_mem,Finset.mem_insert,Finset.mem_singleton,Finset.card_le_card,Finset.card_pairhave hD0card : ((D.erase s).erase t).card = D.card - 2 := by have ht_erase : t ∈ D.erase s := Finset.mem_erase.mpr ⟨hst.symm, htD⟩ rw [Finset.card_erase_of_mem ht_erase, Finset.card_erase_of_mem hsD] omega have hD2 : 2 ≤ D.card := by have hsub : ({s, t} : Finset { s : Finset V // s.card = 2 }) ⊆ D := by intro u hu rw [Finset.mem_insert, Finset.mem_singleton] at hu rcases hu with rfl | rfl · exact hsD · exact htD have h := Finset.card_le_card hsub rwa [Finset.card_pair hst] at h omega
G.ne_of_adj- In a simple graph, two adjacent vertices are distinct.
G.adj_comm- Adjacency in a simple graph is symmetric: u is adjacent to v if and only if v is adjacent to u.
Nat.sInf_le- The infimum of a set of natural numbers is at most any element of that set.
Or.inr- From B, deduce A ∨ B.
Or.inl- From A, deduce A ∨ B.
mul_comm- Multiplication is commutative: a * b = b * a.
Finset.card_biUnion_le- The cardinality of a union of sets over an index set is at most the sum of their cardinalities.
Finset.sum_congr- Two sums over the same finite set are equal if their summands agree on every element.
Finset.sum_const- Summing a constant value b over a finite set s yields |s| • b.
Finset.card_le_one- A finite set has cardinality at most 1 if and only if any two of its elements are equal.
Finset.card_le_one.mp- If a finite set has cardinality at most 1, then any two of its elements are equal.
Finset.card_pair- If a ≠ b, then the pair {a, b} has cardinality 2.
Finset.card_pos.mp- If a finite set has strictly positive cardinality, it is nonempty.
Finset.card_eq_one.mp- If a finite set has cardinality 1, it is a singleton {a}.
Finset.mem_symmDiff- An element belongs to the symmetric difference s ∆ t if and only if it belongs to s \ t or t \ s.
Finset.mem_insert- An element belongs to {a} ∪ s if and only if it equals a or belongs to s.
Finset.mem_insert.mp- If an element belongs to {a} ∪ s, then it equals a or belongs to s.
Finset.mem_singleton- An element belongs to {a} if and only if it equals a.
Finset.mem_singleton_self- An element a belongs to {a}.
Finset.mem_insert_self- An element a belongs to {a} ∪ s.
Finset.card_insert_of_notMem- Inserting an element not in s increases the cardinality of s by 1.
Finset.card_insert_le- Inserting an element into a finite set increases its cardinality by at most 1.
Finset.card_singleton- A singleton set {a} has cardinality 1.
Finset.card_le_card- If s ⊆ t, then |s| ≤ |t|.
Finset.eq_of_subset_of_card_le- If s ⊆ t and |t| ≤ |s|, then s = t.
Finset.card_sdiff_add_card_eq_card- If s ⊆ t, then |t \ s| + |s| = |t|.
Finset.subset_univ- Every finite subset of a finite type is a subset of the universal set univ.
Finset.card_univ- The cardinality of univ for a finite type α equals Fintype.card α.
Finset.mem_univ- Every element of a finite type belongs to the universal set univ.
Finset.mem_sdiff.mp- If x ∈ s \ t, then x ∈ s and x ∉ t.
Finset.mem_sdiff.mpr- If x ∈ s and x ∉ t, then x ∈ s \ t.
Finset.mem_biUnion.mp- If x ∈ ⋃_{a ∈ s} t(a), then there exists a ∈ s with x ∈ t(a).
Finset.mem_biUnion.mpr- If there exists a ∈ s such that x ∈ t(a), then x ∈ ⋃_{a ∈ s} t(a).
Finset.card_erase_of_mem- Removing an element from a set s decreases its cardinality by 1.
Finset.mem_erase.mp- If x belongs to s with a erased, then x ≠ a and x ∈ s.
Finset.mem_erase.mpr- If x ≠ a and x ∈ s, then x belongs to s with a erased.
Finset.insert_erase- If a ∈ s, then inserting a into s with a erased recovers s.
Finset.disjoint_left- Two sets are disjoint if and only if no element of the first belongs to the second.
Finset.symmDiff_eq_union- If s and t are disjoint, then their symmetric difference is their union s ∪ t.
Finset.card_union_of_disjoint- If s and t are disjoint, then |s ∪ t| = |s| + |t|.
Finset.card_union_le- The cardinality of the union s ∪ t is at most |s| + |t|.
Finset.mem_union- An element belongs to s ∪ t if and only if it belongs to s or to t.
- The theorem statement uses integer division `(Fintype.card V + 1) / 2 ≤ D.card` to express ⌈|V|/2⌉ ≤ |D| within natural numbers.
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.
/-- Every dominating set of the 2-token graph F_2(G) has cardinality at least ceil(n/2) when G has domination number at least 2. -/theorem two_token_dominating_set_card_ge_ceil_half {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (hγ : 2 ≤ simple_graph_domination_number G) (D : Finset { s : Finset V // s.card = 2 }) (hD : simple_graph_is_dominating (token_graph G 2) (D : Set { s : Finset V // s.card = 2 })) : (Fintype.card V + 1) / 2 ≤ D.card := by classical set U : Finset V := D.biUnion (fun s => s.val) with hUdef have hsubU : ∀ s ∈ D, s.val ⊆ U := by intro s hs v hv rw [hUdef] exact Finset.mem_biUnion.mpr ⟨s, hs, hv⟩ have hUle : U.card ≤ 2 * D.card := by calc U.card ≤ ∑ s ∈ D, (s.val).card := Finset.card_biUnion_le _ = ∑ _s ∈ D, 2 := by apply Finset.sum_congr rfl intro s _ exact s.property _ = 2 * D.card := by simp [Finset.sum_const, mul_comm] have hcompl : (Finset.univ \ U).card ≤ 1 := by rw [Finset.card_le_one] intro x hx y hy by_contra hxy have hxU : x ∉ U := (Finset.mem_sdiff.mp hx).2 have hyU : y ∉ U := (Finset.mem_sdiff.mp hy).2 have hcard2 : ({x, y} : Finset V).card = 2 := Finset.card_pair hxy rcases hD (⟨{x,y}, hcard2⟩ : {s : Finset V // s.card = 2}) with hzD | ⟨u, huD, hadj⟩ · apply hxU rw [hUdef] exact Finset.mem_biUnion.mpr ⟨_, hzD, by simp⟩ · obtain ⟨p, q, hpq, hdiff⟩ := hadj have huU : ∀ v ∈ u.val, v ∈ U := hsubU u huD have hpos : 0 < u.val.card := by rw [u.property]; norm_num obtain ⟨a, ha⟩ := Finset.card_pos.mp hpos have haU : a ∈ U := huU a ha have hax : a ≠ x := fun h => hxU (h ▸ haU) have hay : a ≠ y := fun h => hyU (h ▸ haU) have hdiff' : symmDiff u.val ({x, y} : Finset V) = {p, q} := hdiff have hxS : x ∈ symmDiff u.val ({x, y} : Finset V) := by rw [Finset.mem_symmDiff] exact Or.inr ⟨by simp, fun hxmem => hxU (huU x hxmem)⟩ have hyS : y ∈ symmDiff u.val ({x, y} : Finset V) := by rw [Finset.mem_symmDiff] exact Or.inr ⟨by simp, fun hymem => hyU (huU y hymem)⟩ have haS : a ∈ symmDiff u.val ({x, y} : Finset V) := by rw [Finset.mem_symmDiff] refine Or.inl ⟨ha, ?_⟩ intro hav rcases Finset.mem_insert.mp hav with h | h · exact hax h · rw [Finset.mem_singleton] at h exact hay h have hsub : ({a, x, y} : Finset V) ⊆ ({p, q} : Finset V) := by intro v hv rw [← hdiff'] rcases Finset.mem_insert.mp hv with rfl | hv · exact haS rcases Finset.mem_insert.mp hv with rfl | hv · exact hxS · rw [Finset.mem_singleton] at hv subst hv exact hyS have h3 : ({a, x, y} : Finset V).card = 3 := by rw [Finset.card_insert_of_notMem (by simp [hax, hay]), Finset.card_insert_of_notMem (by simp [hxy]), Finset.card_singleton] have h2 : ({p, q} : Finset V).card = 2 := Finset.card_pair (G.ne_of_adj hpq) have := Finset.card_le_card hsub omega have hsplit : Fintype.card V = U.card + (Finset.univ \ U).card := by have h := Finset.card_sdiff_add_card_eq_card (Finset.subset_univ U) rw [Finset.card_univ] at h omega suffices hmain : Fintype.card V ≤ 2 * D.card by omega by_contra hlt have hn : Fintype.card V = 2 * D.card + 1 := by omega have hUeq : U.card = 2 * D.card := by omega have hcompeq : (Finset.univ \ U).card = 1 := by omega have hWpos : 0 < (Finset.univ \ U).card := by omega obtain ⟨w, hw⟩ := Finset.card_pos.mp hWpos have hwU : w ∉ U := (Finset.mem_sdiff.mp hw).2 have hWuniq : ∀ x ∈ Finset.univ \ U, x = w := by have h := Finset.card_le_one.mp hcompl exact fun x hx => h x hx w hw have hznondom : ∃ z : V, z ≠ w ∧ ¬ G.Adj w z := by by_contra h push Not at h have hdom : simple_graph_is_dominating G (({w} : Finset V) : Set V) := by intro v by_cases hv : v = w · left; simp [hv] · right; exact ⟨w, by simp, h v hv⟩ have hmem : 1 ∈ {k : ℕ | ∃ S : Finset V, simple_graph_is_dominating G (S : Set V) ∧ S.card = k} := ⟨{w}, hdom, by simp⟩ have hle : simple_graph_domination_number G ≤ 1 := Nat.sInf_le hmem omega obtain ⟨z, hzw, hzw'⟩ := hznondom have hzU : z ∈ U := by by_contra hz have : z ∈ Finset.univ \ U := Finset.mem_sdiff.mpr ⟨Finset.mem_univ z, hz⟩ exact hzw (hWuniq z this) obtain ⟨s, hsD, hzs⟩ := Finset.mem_biUnion.mp hzU have hsval : s.val ⊆ U := hsubU s hsD have hscard : (s.val.erase z).card = 1 := by rw [Finset.card_erase_of_mem hzs, s.property] obtain ⟨z', hz'E⟩ := Finset.card_eq_one.mp hscard have hz'erase : z' ∈ s.val.erase z := by rw [hz'E]; exact Finset.mem_singleton_self z' have hz'ne : z' ≠ z := (Finset.mem_erase.mp hz'erase).1 have hz'mem : z' ∈ s.val := (Finset.mem_erase.mp hz'erase).2 have hs_eq : s.val = {z, z'} := by conv_lhs => rw [← Finset.insert_erase hzs] rw [hz'E] have hz'U : z' ∈ U := hsval hz'mem have hwz' : w ≠ z' := fun h => hwU (h ▸ hz'U) set y : { s : Finset V // s.card = 2 } := ⟨{w, z'}, Finset.card_pair hwz'⟩ with hydef have hyval : y.val = ({w, z'} : Finset V) := rfl have hynd : y ∉ D := by intro hy apply hwU rw [hUdef] exact Finset.mem_biUnion.mpr ⟨y, hy, by rw [hyval]; simp⟩ have hdomy : ∃ t ∈ D, (token_graph G 2).Adj t y := by rcases hD y with hy | ⟨t, htD, hadj⟩ · exact absurd hy hynd · exact ⟨t, htD, hadj⟩ obtain ⟨t, htD, hadj⟩ := hdomy obtain ⟨p, q, hpq, hdiff⟩ := hadj have htU : ∀ v ∈ t.val, v ∈ U := hsubU t htD have hwt : w ∉ t.val := fun h => hwU (htU w h) have hz't : z' ∈ t.val := by by_contra hz'nt have hdisj : Disjoint t.val y.val := by rw [Finset.disjoint_left] intro v hv hvy rw [hyval] at hvy rcases Finset.mem_insert.mp hvy with rfl | hvy · exact hwt hv · rw [Finset.mem_singleton] at hvy exact hz'nt (hvy ▸ hv) have hsym : symmDiff t.val y.val = t.val ∪ y.val := Finset.symmDiff_eq_union hdisj have hc4 : (t.val ∪ y.val).card = 4 := by rw [Finset.card_union_of_disjoint hdisj, t.property, hyval, Finset.card_pair hwz'] have hc2 : (symmDiff t.val y.val).card = 2 := by rw [hdiff]; exact Finset.card_pair (G.ne_of_adj hpq) rw [hsym] at hc2 omega have hterase : (t.val.erase z').card = 1 := by rw [Finset.card_erase_of_mem hz't, t.property] obtain ⟨b', hb'E⟩ := Finset.card_eq_one.mp hterase have hb'erase : b' ∈ t.val.erase z' := by rw [hb'E]; exact Finset.mem_singleton_self b' have hb'ne : b' ≠ z' := (Finset.mem_erase.mp hb'erase).1 have hb'mem : b' ∈ t.val := (Finset.mem_erase.mp hb'erase).2 have ht_eq : t.val = {z', b'} := by conv_lhs => rw [← Finset.insert_erase hz't] rw [hb'E] have hwS : w ∈ symmDiff t.val y.val := by rw [Finset.mem_symmDiff] exact Or.inr ⟨by rw [hyval]; simp, hwt⟩ have hb'S : b' ∈ symmDiff t.val y.val := by rw [Finset.mem_symmDiff] refine Or.inl ⟨hb'mem, ?_⟩ rw [hyval] simp only [Finset.mem_insert, Finset.mem_singleton, not_or] exact ⟨fun h => hwU (h ▸ htU b' hb'mem), hb'ne⟩ have hwq : w ∈ ({p, q} : Finset V) := by rw [← hdiff]; exact hwS have hb'q : b' ∈ ({p, q} : Finset V) := by rw [← hdiff]; exact hb'S have hwb' : w ≠ b' := fun h => hwU (h ▸ htU b' hb'mem) have hsubpq : ({w, b'} : Finset V) ⊆ ({p, q} : Finset V) := by intro v hv rcases Finset.mem_insert.mp hv with rfl | hv · exact hwq · rw [Finset.mem_singleton] at hv subst hv exact hb'q have heq : ({w, b'} : Finset V) = {p, q} := by apply Finset.eq_of_subset_of_card_le hsubpq rw [Finset.card_pair (G.ne_of_adj hpq), Finset.card_pair hwb'] have hwadj : G.Adj w b' := by have hp : p ∈ ({w, b'} : Finset V) := by rw [heq]; exact Finset.mem_insert_self p {q} have hq : q ∈ ({w, b'} : Finset V) := by rw [heq]; simp rw [Finset.mem_insert, Finset.mem_singleton] at hp hq rcases hp with hp | hp <;> rcases hq with hq | hq · exact absurd (hp.trans hq.symm) (G.ne_of_adj hpq) · rw [hp, hq] at hpq; exact hpq · rw [hp, hq] at hpq; exact (G.adj_comm b' w).mp hpq · exact absurd (hp.trans hq.symm) (G.ne_of_adj hpq) by_cases hbz : b' = z · exact hzw' (hbz ▸ hwadj) · have hst : s ≠ t := by intro hst_eq have hzt : z ∈ t.val := by rw [← hst_eq]; exact hzs rw [ht_eq] at hzt rcases Finset.mem_insert.mp hzt with h | h · exact hz'ne h.symm · rw [Finset.mem_singleton] at h exact hbz h.symm have hcover : U ⊆ ({z, z', b'} : Finset V) ∪ ((D.erase s).erase t).biUnion (fun u => u.val) := by intro v hv rw [hUdef] at hv obtain ⟨u, huD, hvu⟩ := Finset.mem_biUnion.mp hv rw [Finset.mem_union] by_cases hus : u = s · left rw [hus, hs_eq] at hvu simp only [Finset.mem_insert, Finset.mem_singleton] at hvu ⊢ tauto · by_cases hut : u = t · left rw [hut, ht_eq] at hvu simp only [Finset.mem_insert, Finset.mem_singleton] at hvu ⊢ tauto · right exact Finset.mem_biUnion.mpr ⟨u, Finset.mem_erase.mpr ⟨hut, Finset.mem_erase.mpr ⟨hus, huD⟩⟩, hvu⟩ have hcard_cover : U.card ≤ 3 + 2 * ((D.erase s).erase t).card := by have h1 : U.card ≤ (({z, z', b'} : Finset V) ∪ ((D.erase s).erase t).biUnion (fun u => u.val)).card := Finset.card_le_card hcover have h2 : (({z, z', b'} : Finset V) ∪ ((D.erase s).erase t).biUnion (fun u => u.val)).card ≤ ({z, z', b'} : Finset V).card + (((D.erase s).erase t).biUnion (fun u => u.val)).card := Finset.card_union_le _ _ have h3 : ({z, z', b'} : Finset V).card ≤ 3 := by have ha1 := Finset.card_insert_le z ({z', b'} : Finset V) have ha2 := Finset.card_insert_le z' ({b'} : Finset V) simp only [Finset.card_singleton] at ha1 ha2 omega have h4 : (((D.erase s).erase t).biUnion (fun u => u.val)).card ≤ 2 * ((D.erase s).erase t).card := by calc _ ≤ ∑ u ∈ (D.erase s).erase t, (u.val).card := Finset.card_biUnion_le _ = ∑ _u ∈ (D.erase s).erase t, 2 := by apply Finset.sum_congr rfl intro u _ exact u.property _ = 2 * ((D.erase s).erase t).card := by simp [Finset.sum_const, mul_comm] omega have hD0card : ((D.erase s).erase t).card = D.card - 2 := by have ht_erase : t ∈ D.erase s := Finset.mem_erase.mpr ⟨hst.symm, htD⟩ rw [Finset.card_erase_of_mem ht_erase, Finset.card_erase_of_mem hsD] omega have hD2 : 2 ≤ D.card := by have hsub : ({s, t} : Finset { s : Finset V // s.card = 2 }) ⊆ D := by intro u hu rw [Finset.mem_insert, Finset.mem_singleton] at hu rcases hu with rfl | rfl · exact hsD · exact htD have h := Finset.card_le_card hsub rwa [Finset.card_pair hst] at h omega