AFTD Auto-Formalizing Theoretical Domains

two_token_dominating_set_card_ge_ceil_half

theoremverified

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

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|.

  1. 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).

    lines 7–12

    uses Finset.mem_biUnion.mpr

      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⟩
  2. 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).

    lines 13–20

    uses Finset.card_biUnion_le, Finset.sum_congr, Finset.sum_const, mul_comm

      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]
  3. 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.

    lines 21–70

    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_card

      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
  4. 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.

    lines 71–75

    uses Finset.card_sdiff_add_card_eq_card, Finset.subset_univ, Finset.card_univ

      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
  5. 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).

    lines 76–85

    uses Finset.card_pos.mp, Finset.mem_sdiff.mp, Finset.card_le_one.mp

      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
  6. 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.

    lines 86–98

    uses Nat.sInf_le

      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
  7. 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'.

    lines 99–115

    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_erase

      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)
  8. 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.

    lines 116–127

    uses Finset.card_pair, Finset.mem_biUnion.mpr

      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
  9. 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).

    lines 128–156

    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_erase

      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]
  10. 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.

    lines 157–190

    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_comm

      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
  11. 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).

    lines 191–234

    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_comm

          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
  12. 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.

    lines 235–248

    uses Finset.mem_erase.mpr, Finset.card_erase_of_mem, Finset.mem_insert, Finset.mem_singleton, Finset.card_le_card, Finset.card_pair

        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
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.

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

/-- 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
See it in the graphDiscuss this resultChallenge it