AFTD Auto-Formalizing Theoretical Domains

two_token_domination_number_even_matching_le

theoremverifiedformalization

Let G be a finite simple graph on vertex type V whose complement graph Gᶜ is 1-regular. Then the domination number of the 2-token graph F_2(G) is at most Fintype.card V / 2.

Statement

open scoped Classical in
theorem two_token_domination_number_even_matching_le {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) (hreg : Gᶜ.IsRegularOfDegree 1) :
    simple_graph_domination_number (token_graph G 2) ≤ Fintype.card V / 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

For any finite type V with decidable equality and any simple graph G on V, if the complement graph Gᶜ is 1-regular (i.e., every vertex has degree 1 in Gᶜ), then the domination number of the 2-token graph of G is at most Fintype.card V / 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 proof constructs an explicit dominating set D in the 2-token graph F₂(G) using the 1-factor structure of the complement graph Gᶜ. Because Gᶜ is 1-regular, each vertex v has a unique complement-neighbor p(v), giving a fixed-point-free involution that partitions V into |V|/2 disjoint pairs. Taking D to be the collection of these pairs {v, p(v)} yields a subset of size |V|/2. Any other pair {a, b} not in D has b ≠ p(a), and the non-adjacency of b and p(a) in Gᶜ forces an edge between them in G, making {a, b} adjacent in F₂(G) to the pair {a, p(a)} ∈ D; thus D dominates the graph.

  1. Every vertex v in V has a unique neighbor in the complement graph Gᶜ.

    Because Gᶜ is 1-regular by assumption, the degree of each vertex v in Gᶜ is 1. The degree equals the cardinality of the neighbor finset (by SimpleGraph.card_neighborFinset_eq_degree), so the neighbor finset has size 1 and is therefore a singleton {w} (by Finset.card_eq_one.mp). By SimpleGraph.mem_neighborFinset, w is adjacent to v in Gᶜ, and any complement-neighbor y must lie in {w} and hence equal w.

    lines 6–19

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

      classical
      -- The complement is 1-regular, so every vertex has a unique complement-neighbour.
      have hex : ∀ v : V, ∃! w, Gᶜ.Adj v w := by
        intro v
        have hdeg : (Gᶜ).degree v = 1 := hreg v
        rw [← SimpleGraph.card_neighborFinset_eq_degree] at hdeg
        obtain ⟨w, hw⟩ := Finset.card_eq_one.mp hdeg
        refine ⟨w, ?_, ?_⟩
        · have : w ∈ Gᶜ.neighborFinset v := by rw [hw]; simp
          exact (SimpleGraph.mem_neighborFinset _ _ _).mp this
        · intro y hy
          have : y ∈ Gᶜ.neighborFinset v := (SimpleGraph.mem_neighborFinset _ _ _).mpr hy
          rw [hw] at this
          simpa using this
  2. There is a fixed-point-free involution p : V → V sending each vertex to its unique complement-neighbor.

    Using classical choice (Classical.choose and Classical.choose_spec), let p(v) be the unique complement-neighbor of v. Because simple graphs are loopless, p(v) ≠ v. Since adjacency in Gᶜ is symmetric, v is a complement-neighbor of p(v), so by uniqueness of complement-neighbors, p(p(v)) = v.

    lines 20–28

    uses Classical.choose, Classical.choose_spec

      let p : V → V := fun v => Classical.choose (hex v)
      have hp_adj : ∀ v, Gᶜ.Adj v (p v) := fun v => (Classical.choose_spec (hex v)).1
      have hp_uniq : ∀ v w, Gᶜ.Adj v w → w = p v := fun v w h => (Classical.choose_spec (hex v)).2 w h
      have hp_ne : ∀ v, p v ≠ v := by
        intro v h
        exact (Gᶜ).ne_of_adj (hp_adj v) h.symm
      have hp_invol : ∀ v, p (p v) = v := by
        intro v
        exact (hp_uniq (p v) v (hp_adj v).symm).symm
  3. The map f(v) = {v, p v} produces 2-element subsets, and the fiber over f(v) is precisely {v, p v}.

    Because p(v) ≠ v, the pair {v, p(v)} has cardinality 2 (by Finset.card_pair), defining a map f from V to the vertex set of the 2-token graph. If f(u) = f(v), then u ∈ f(u) = f(v) = {v, p(v)} (unfolded via Finset.mem_filter, Finset.mem_univ, true_and), forcing u = v or u = p(v) (by Finset.mem_insert, Finset.mem_singleton). Conversely, f(p(v)) = {p(v), p(p(v))} = {p(v), v} = {v, p(v)} = f(v) by the involution property and symmetry of pairs (Finset.pair_comm, Subtype.ext).

    lines 29–44

    uses Finset.card_pair, Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_insert, Finset.mem_singleton, Subtype.ext, Finset.pair_comm

      -- The pairing as a map on 2-element subsets.
      let f : V → {s : Finset V // s.card = 2} := fun v => ⟨{v, p v}, Finset.card_pair (hp_ne v).symm⟩
      have hfib : ∀ v, (Finset.univ.filter (fun u => f u = f v)) = ({v, p v} : Finset V) := by
        intro v
        ext u
        simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_insert, Finset.mem_singleton]
        constructor
        · intro h
          have hmem : u ∈ (f u).val := by simp [f]
          rw [h] at hmem
          simpa [f] using hmem
        · rintro (rfl | rfl)
          · rfl
          · apply Subtype.ext
            change ({p v, p (p v)} : Finset V) = {v, p v}
            rw [hp_invol, Finset.pair_comm]
  4. The image D = f(V) has cardinality |V| / 2.

    The set D is defined as the image of V under f (using Finset.mem_image.mpr, Finset.mem_univ). By fiberwise summation (Finset.card_eq_sum_card_fiberwise, Finset.card_univ), the size of V is the sum of the fiber cardinalities over b ∈ D. Every b ∈ D is of the form f(v) (by Finset.mem_image.mp), whose fiber is {v, p(v)} of size 2 (by Finset.card_pair). Summing 2 over D gives |V| = 2 * |D| (via Finset.sum_congr and Finset.sum_const), and dividing by 2 yields |D| = |V| / 2 (by Nat.mul_div_cancel).

    lines 45–60

    uses Finset.mem_image.mpr, Finset.mem_univ, Finset.card_eq_sum_card_fiberwise, Finset.card_univ, Finset.mem_image.mp, Finset.card_pair, Finset.sum_congr, Finset.sum_const, Nat.mul_div_cancel

      let D : Finset {s : Finset V // s.card = 2} := Finset.univ.image f
      -- `D` has exactly half as many elements as `V`.
      have hcard : D.card = Fintype.card V / 2 := by
        have hmaps : Set.MapsTo f (↑(Finset.univ : Finset V)) (↑D) := by
          intro x hx
          exact Finset.mem_image.mpr ⟨x, Finset.mem_univ x, rfl⟩
        have hsum := Finset.card_eq_sum_card_fiberwise hmaps
        rw [Finset.card_univ] at hsum
        have hfiber2 : ∀ b ∈ D, (Finset.univ.filter (fun a => f a = b)).card = 2 := by
          intro b hb
          obtain ⟨v, hv, rfl⟩ := Finset.mem_image.mp hb
          rw [hfib v, Finset.card_pair (hp_ne v).symm]
        have h1 : Fintype.card V = D.card * 2 := by
          rw [hsum, Finset.sum_congr rfl hfiber2]
          simp [Finset.sum_const]
        rw [h1, Nat.mul_div_cancel _ (by norm_num : 0 < 2)]
  5. For distinct vertices a, b with b ≠ p(a), the symmetric difference of {a, p a} and {a, b} is {b, p a}.

    By definition of symmetric difference (Finset.mem_symmDiff, Finset.mem_insert, Finset.mem_singleton), an element c belongs to {a, p(a)} ∆ {a, b} if and only if it is in exactly one of the two sets. Checking the cases c = a, c = p(a), c = b, or c distinct from all three reveals that the shared element a cancels out, while b and p(a) each belong to only one of the sets, leaving {b, p(a)}.

    lines 61–75

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

      -- Symmetric-difference computation used for the domination step.
      have hpair : ∀ a b : V, a ≠ b → b ≠ p a →
          symmDiff ({a, p a} : Finset V) {a, b} = {b, p a} := by
        intro a b hab hbpa
        have hapa : a ≠ p a := fun h => (hp_ne a) h.symm
        ext c
        rw [Finset.mem_symmDiff]
        simp only [Finset.mem_insert, Finset.mem_singleton]
        by_cases hca : c = a
        · rw [hca]; simp [hapa, hapa.symm, hab, hab.symm, hbpa, hbpa.symm]
        · by_cases hcp : c = p a
          · rw [hcp]; simp [hapa, hapa.symm, hab, hab.symm, hbpa, hbpa.symm]
          · by_cases hcb : c = b
            · rw [hcb]; simp [hapa, hapa.symm, hab, hab.symm, hbpa, hbpa.symm]
            · simp [hca, hcp, hcb]
  6. D is a dominating set of the 2-token graph F₂(G).

    Let s be a vertex of F₂(G), so s = {a, b} with a ≠ b (by Finset.card_eq_two.mp). If a and b are adjacent in Gᶜ, then b = p(a) by uniqueness, so s = {a, p(a)} = f(a) ∈ D (Finset.mem_image.mpr, Finset.mem_univ, Subtype.ext). If a and b are not complement-adjacent, then b ≠ p(a). Furthermore, b must be adjacent to p(a) in G; otherwise they would be adjacent in Gᶜ, forcing b = p(p(a)) = a, a contradiction. Since {a, p(a)} ∆ {a, b} = {b, p(a)} is an edge of G, s is adjacent to f(a) ∈ D in the 2-token graph.

    lines 76–98

    uses Finset.card_eq_two.mp, Finset.mem_image.mpr, Finset.mem_univ, Subtype.ext

      -- `D` is a dominating set of the 2-token graph.
      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 h : Gᶜ.Adj a b
        · left
          have hpa : p a = b := (hp_uniq a b h).symm
          refine Finset.mem_image.mpr ⟨a, Finset.mem_univ a, ?_⟩
          apply Subtype.ext
          change ({a, p a} : Finset V) = {a, b}
          rw [hpa]
        · right
          have hbpa : b ≠ p a := by
            intro hb
            exact h (by rw [hb]; exact hp_adj a)
          have hgadj : G.Adj b (p a) := by
            by_contra hg
            have hc : Gᶜ.Adj b (p a) := ⟨hbpa, hg⟩
            have hba : b = a := by rw [hp_uniq (p a) b hc.symm, hp_invol]
            exact hab hba.symm
          exact ⟨f a, Finset.mem_image.mpr ⟨a, Finset.mem_univ a, rfl⟩, b, p a, hgadj,
            hpair a b hab hbpa⟩
  7. The domination number of F₂(G) is at most |V| / 2.

    The domination number is defined as the infimum of the cardinalities of all dominating sets of the token graph. Since D is a dominating set of size |V| / 2, this infimum is at most |D| = |V| / 2 (by Nat.sInf_le).

    lines 99–101

    uses Nat.sInf_le

      unfold simple_graph_domination_number
      rw [← hcard]
      exact Nat.sInf_le ⟨D, hdom, rfl⟩
SimpleGraph.card_neighborFinset_eq_degree
The degree of a vertex in a simple graph equals the cardinality of its neighbor finset.
Finset.card_eq_one.mp
A finset has cardinality 1 if and only if it is a singleton {a}.
SimpleGraph.mem_neighborFinset
A vertex belongs to the neighbor finset of v if and only if it is adjacent to v in the graph.
Classical.choose
Given an existence proof, selects a witness element satisfying the predicate.
Classical.choose_spec
The witness chosen by Classical.choose satisfies the given predicate.
Finset.card_pair
The pair set {a, b} has cardinality 2 if and only if a ≠ b.
Finset.mem_filter
An element belongs to a filtered finset if and only if it belongs to the finset and satisfies the predicate.
Finset.mem_univ
Every element of a finite type belongs to the universal finset univ.
true_and
The conjunction of True with any proposition p simplifies to p.
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 the singleton {a} if and only if it equals a.
Subtype.ext
Two subtype elements are equal if their underlying values are equal.
Finset.pair_comm
The unordered pair {a, b} equals {b, a}.
Finset.mem_image.mpr
An element is in the image finset f(s) if it is the image of some element in s.
Finset.card_eq_sum_card_fiberwise
The cardinality of a finset s equals the sum of the cardinalities of its fibers under a map f.
Finset.card_univ
The cardinality of the universal finset is the cardinality of the underlying finite type.
Finset.mem_image.mp
If an element is in the image finset f(s), then it is the image of some element in s.
Finset.sum_congr
Two sums over equal finsets are equal if their summands agree on every element.
Finset.sum_const
The sum of a constant value over a finset equals the cardinality of the finset multiplied by the constant.
Nat.mul_div_cancel
Multiplying a natural number by a positive integer n and then dividing by n gives back the original number.
Finset.mem_symmDiff
An element belongs to the symmetric difference s ∆ t if and only if it belongs to exactly one of s or t.
Finset.card_eq_two.mp
A finset has cardinality 2 if and only if it is of the form {x, y} with x ≠ y.
Nat.sInf_le
The infimum of a set of natural numbers is at most any member of the 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

open scoped Classical in/-- If the complement of G is 1-regular (a 1-factor), then the domination number of F_2(G) is at most n / 2. -/theorem two_token_domination_number_even_matching_le {V : Type*} [Fintype V] [DecidableEq V]    (G : SimpleGraph V) (hreg : Gᶜ.IsRegularOfDegree 1) :    simple_graph_domination_number (token_graph G 2) ≤ Fintype.card V / 2 := by  classical  -- The complement is 1-regular, so every vertex has a unique complement-neighbour.  have hex : ∀ v : V, ∃! w, Gᶜ.Adj v w := by    intro v    have hdeg : (Gᶜ).degree v = 1 := hreg v    rw [← SimpleGraph.card_neighborFinset_eq_degree] at hdeg    obtain ⟨w, hw⟩ := Finset.card_eq_one.mp hdeg    refine ⟨w, ?_, ?_⟩    · have : w ∈ Gᶜ.neighborFinset v := by rw [hw]; simp      exact (SimpleGraph.mem_neighborFinset _ _ _).mp this    · intro y hy      have : y ∈ Gᶜ.neighborFinset v := (SimpleGraph.mem_neighborFinset _ _ _).mpr hy      rw [hw] at this      simpa using this  let p : V → V := fun v => Classical.choose (hex v)  have hp_adj : ∀ v, Gᶜ.Adj v (p v) := fun v => (Classical.choose_spec (hex v)).1  have hp_uniq : ∀ v w, Gᶜ.Adj v w → w = p v := fun v w h => (Classical.choose_spec (hex v)).2 w h  have hp_ne : ∀ v, p v ≠ v := by    intro v h    exact (Gᶜ).ne_of_adj (hp_adj v) h.symm  have hp_invol : ∀ v, p (p v) = v := by    intro v    exact (hp_uniq (p v) v (hp_adj v).symm).symm  -- The pairing as a map on 2-element subsets.  let f : V → {s : Finset V // s.card = 2} := fun v => ⟨{v, p v}, Finset.card_pair (hp_ne v).symm⟩  have hfib : ∀ v, (Finset.univ.filter (fun u => f u = f v)) = ({v, p v} : Finset V) := by    intro v    ext u    simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_insert, Finset.mem_singleton]    constructor    · intro h      have hmem : u ∈ (f u).val := by simp [f]      rw [h] at hmem      simpa [f] using hmem    · rintro (rfl | rfl)      · rfl      · apply Subtype.ext        change ({p v, p (p v)} : Finset V) = {v, p v}        rw [hp_invol, Finset.pair_comm]  let D : Finset {s : Finset V // s.card = 2} := Finset.univ.image f  -- `D` has exactly half as many elements as `V`.  have hcard : D.card = Fintype.card V / 2 := by    have hmaps : Set.MapsTo f (↑(Finset.univ : Finset V)) (↑D) := by      intro x hx      exact Finset.mem_image.mpr ⟨x, Finset.mem_univ x, rfl⟩    have hsum := Finset.card_eq_sum_card_fiberwise hmaps    rw [Finset.card_univ] at hsum    have hfiber2 : ∀ b ∈ D, (Finset.univ.filter (fun a => f a = b)).card = 2 := by      intro b hb      obtain ⟨v, hv, rfl⟩ := Finset.mem_image.mp hb      rw [hfib v, Finset.card_pair (hp_ne v).symm]    have h1 : Fintype.card V = D.card * 2 := by      rw [hsum, Finset.sum_congr rfl hfiber2]      simp [Finset.sum_const]    rw [h1, Nat.mul_div_cancel _ (by norm_num : 0 < 2)]  -- Symmetric-difference computation used for the domination step.  have hpair : ∀ a b : V, a ≠ b → b ≠ p a →      symmDiff ({a, p a} : Finset V) {a, b} = {b, p a} := by    intro a b hab hbpa    have hapa : a ≠ p a := fun h => (hp_ne a) h.symm    ext c    rw [Finset.mem_symmDiff]    simp only [Finset.mem_insert, Finset.mem_singleton]    by_cases hca : c = a    · rw [hca]; simp [hapa, hapa.symm, hab, hab.symm, hbpa, hbpa.symm]    · by_cases hcp : c = p a      · rw [hcp]; simp [hapa, hapa.symm, hab, hab.symm, hbpa, hbpa.symm]      · by_cases hcb : c = b        · rw [hcb]; simp [hapa, hapa.symm, hab, hab.symm, hbpa, hbpa.symm]        · simp [hca, hcp, hcb]  -- `D` is a dominating set of the 2-token graph.  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 h : Gᶜ.Adj a b    · left      have hpa : p a = b := (hp_uniq a b h).symm      refine Finset.mem_image.mpr ⟨a, Finset.mem_univ a, ?_⟩      apply Subtype.ext      change ({a, p a} : Finset V) = {a, b}      rw [hpa]    · right      have hbpa : b ≠ p a := by        intro hb        exact h (by rw [hb]; exact hp_adj a)      have hgadj : G.Adj b (p a) := by        by_contra hg        have hc : Gᶜ.Adj b (p a) := ⟨hbpa, hg⟩        have hba : b = a := by rw [hp_uniq (p a) b hc.symm, hp_invol]        exact hab hba.symm      exact ⟨f a, Finset.mem_image.mpr ⟨a, Finset.mem_univ a, rfl⟩, b, p a, hgadj,        hpair a b hab hbpa⟩  unfold simple_graph_domination_number  rw [← hcard]  exact Nat.sInf_le ⟨D, hdom, rfl⟩
See it in the graphDiscuss this resultChallenge it