AFTD Auto-Formalizing Theoretical Domains

two_token_domination_number_odd_p3_matching_le

theoremverifiedformalization

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.

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

    lines 4–16

    uses Finset.mem_symmDiff, Finset.mem_insert, Finset.mem_singleton

      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]
  2. 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ᶜ.

    lines 23–36

    uses SimpleGraph.card_neighborFinset_eq_degree, Finset.card_eq_one.mp, SimpleGraph.mem_neighborFinset

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

    lines 37–49

    uses dif_neg, Classical.choose_spec

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

    lines 51–61

    uses SimpleGraph.card_neighborFinset_eq_degree, Finset.card_eq_two.mp, SimpleGraph.mem_neighborFinset, SimpleGraph.ne_of_adj

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

    lines 63–100

    uses Finset.mem_filter, Finset.mem_univ, SimpleGraph.mem_neighborFinset, Finset.mem_insert, Finset.mem_singleton, SimpleGraph.ne_of_adj

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

    lines 102–112

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

    lines 114–152

    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_cancel

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

    lines 154–165

    uses Finset.card_insert_of_notMem, Finset.card_singleton, Finset.card_sdiff_of_subset, Finset.subset_univ, Finset.card_univ, Finset.card_le_card

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

    lines 167–220

    uses Finset.card_pair, dif_pos, Finset.mem_insert, Finset.mem_singleton, Finset.mem_filter, Finset.card_insert_of_notMem

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

    lines 222–256

    uses Finset.card_pair, dif_pos, Subtype.ext, Finset.mem_filter, two_token_domination_number_odd_p3_matching_le_symmDiff_pair_pair

      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]
  11. 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₃}.

    lines 258–310

    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_pair

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

    lines 311–313

    uses Nat.sInf_le

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

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

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