AFTD Auto-Formalizing Theoretical Domains

two_token_k2_nminus2_has_dominating_set

theoremverified

For every integer n ≥ 4, there exists a dominating set of the 2-token graph F_2(K_{2,n-2}) of cardinality at most n - 2.

Statement

theorem two_token_k2_nminus2_has_dominating_set (n : ℕ) (hn : 4 ≤ n) :
    ∃ S : Finset { s : Finset (Fin 2 ⊕ Fin (n - 2)) // s.card = 2 },
      simple_graph_is_dominating (token_graph (completeBipartiteGraph (Fin 2) (Fin (n - 2))) 2) (S : Set _) ∧
      S.card ≤ n - 2
Source
arXiv:2611.15124 Proposition 3.1 -- Domination in token graphs of graphs with domination number two
Verified
16 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • 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.
  • two_token_kmn_ll_vertexThe LL vertex {x,y} determined by two distinct left vertices x != y.
  • two_token_kmn_lr_vertexThe LR vertex {x,y} determined by a left vertex x and a right vertex y.

Read back from the Lean

For every natural number $n \ge 4$, there exists a finite set $S$ of 2-element subsets of $\mathrm{Fin}(2) \oplus \mathrm{Fin}(n - 2)$ such that: 1. $S$ (viewed as a set) is a dominating set of the 2-token graph of the complete bipartite graph $K_{2, n-2}$ (with parts $\mathrm{Fin}(2)$ and $\mathrm{Fin}(n - 2)$); and 2. The cardinality of $S$ is at most $n - 2$.

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

To construct a dominating set of size at most n - 2 for the 2-token graph F_2(K_{2, n-2}), we fix an element z ∈ Fin(n - 2) and choose S to consist of the unique 2-token on the left part, ll = {0, 1}, together with the n - 3 mixed pairs {0, j} for j ≠ z. This set S has cardinality 1 + (n - 3) = n - 2. Any vertex of F_2(K_{2, n-2}) is either in S or dominated by S: {0, 1} and the pairs {0, j} (j ≠ z) are already in S; {0, z} and all pairs {1, b} are adjacent to ll; and any pair {b1, b2} on the right part is adjacent to {0, b2} (if b1 = z) or {0, b1} (if b1 ≠ z).

  1. Any 2-element subset of A ⊕ B is either two distinct elements of A, a mixed pair from A and B, or two distinct elements of B.

    By `Finset.card_eq_two`, a finset s of size 2 is of the form {x, y} with x ≠ y. Case splitting on whether x and y lie in A (via Sum.inl) or B (via Sum.inr) yields the three cases, using `Finset.pair_comm` to reorder the mixed pair when x ∈ B and y ∈ A.

    lines 6–16

    uses Finset.card_eq_two, Finset.pair_comm

      rw [Finset.card_eq_two] at hs
      rcases hs with ⟨x, y, hne, rfl⟩
      rcases x with a1 | b1 <;> rcases y with a2 | b2
      · left
        refine ⟨a1, a2, ?_, rfl⟩
        rintro rfl; exact hne rfl
      · right; left; exact ⟨a1, b2, rfl⟩
      · right; left; refine ⟨a2, b1, ?_⟩; rw [Finset.pair_comm]
      · right; right
        refine ⟨b1, b2, ?_, rfl⟩
        rintro rfl; exact hne rfl
  2. Any pair of distinct elements in Fin 2 embedded into Fin 2 ⊕ Fin k equals {0, 1}.

    Exhaustive case analysis on a1, a2 ∈ Fin 2 using `fin_cases`. The cases where a1 = a2 are impossible by the hypothesis a1 ≠ a2; the case (0, 1) holds by definition; and the case (1, 0) follows by pair commutativity (`Finset.pair_comm`).

    lines 21–26

    uses Finset.pair_comm

      revert hne
      fin_cases a1 <;> fin_cases a2
      · intro h; contradiction
      · intro _; rfl
      · intro _; rw [Finset.pair_comm]; rfl
      · intro h; contradiction
  3. Define a candidate dominating set S of vertices consisting of ll = {0, 1} and the mixed pairs {0, j} for all j ≠ z in Fin(n - 2).

    Since n ≥ 4, n - 2 > 0 by linear arithmetic (`omega`). We pick z = 0 ∈ Fin(n - 2) as a fixed reference element. We define ll as the unique pair of vertices in Fin 2, and lr_part as the image under j ↦ {0, j} of Fin(n - 2) with z removed. We set S = insert ll lr_part and prepare to show S dominates the graph and has size at most n - 2.

    lines 33–39

      have hk : 0 < n - 2 := by omega
      let z : Fin (n - 2) := ⟨0, hk⟩
      let ll : { s : Finset (Fin 2 ⊕ Fin (n - 2)) // s.card = 2 } :=
        two_token_kmn_ll_vertex (0 : Fin 2) (1 : Fin 2) (by decide)
      let lr_part := (Finset.univ.erase z).image (fun j => two_token_kmn_lr_vertex (0 : Fin 2) j)
      let S : Finset { s : Finset (Fin 2 ⊕ Fin (n - 2)) // s.card = 2 } := insert ll lr_part
      refine ⟨S, ?_, ?_⟩
  4. Every vertex whose two tokens both lie in Fin 2 belongs to S.

    We classify an arbitrary vertex v using `two_token_k2_nminus2_has_dominating_set_finset_card_two_cases`. When both tokens lie in Fin 2, lemma `two_token_k2_nminus2_has_dominating_set_fin2_pair_eq` shows that v equals ll as an underlying set, hence v = ll by `Subtype.ext`. Since ll ∈ S by `Finset.mem_insert_self`, v is in S.

    lines 40–52

    uses two_token_k2_nminus2_has_dominating_set_finset_card_two_cases, two_token_k2_nminus2_has_dominating_set_fin2_pair_eq, Subtype.ext, Finset.mem_insert_self

      · intro v
        rcases two_token_k2_nminus2_has_dominating_set_finset_card_two_cases v.val v.property with
          (⟨a1, a2, hne, hs⟩ | ⟨a, b, hs⟩ | ⟨b1, b2, hne, hs⟩)
        · -- Case LL
          left
          have h_eq : v = ll := by
            apply Subtype.ext
            dsimp [ll, two_token_kmn_ll_vertex]
            rw [hs]
            exact two_token_k2_nminus2_has_dominating_set_fin2_pair_eq a1 a2 hne
          rw [h_eq]
          exact Finset.mem_insert_self _ _
        · -- Case LR
  5. The mixed vertex v = {0, z} is adjacent to ll ∈ S. automation

    When v = {a, b} with a = 0 and b = z, the symmetric difference of ll = {0, 1} and v = {0, z} is {1, z}. Since 1 ∈ Fin 2 and z ∈ Fin(n - 2), this is an edge of the complete bipartite graph K_{2, n-2}. Therefore ll is adjacent to v in the 2-token graph. The set equality is discharged by `aesop` after simplifying membership conditions.

    lines 53–67

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

          fin_cases a
          · -- a = 0
            by_cases hb : b = z
            · -- b = z
              subst hb
              right
              refine ⟨ll, Finset.mem_insert_self _ _, ?_⟩
              refine ⟨Sum.inl (1 : Fin 2), Sum.inr z, ?_, ?_⟩
              · dsimp [completeBipartiteGraph]; left; simp
              · ext x
                simp only [Finset.mem_symmDiff, Finset.mem_insert, Finset.mem_singleton]
                rw [hs]
                dsimp [ll, two_token_kmn_ll_vertex]
                aesop
            · -- b ≠ z
  6. Every mixed vertex v = {0, b} with b ≠ z belongs to S.

    When a = 0 and b ≠ z, v is the vertex {0, b} by `Subtype.ext`. Since b ∈ Fin(n - 2) \ {z}, {0, b} belongs to lr_part by `Finset.mem_image_of_mem`, and hence belongs to S by `Finset.mem_insert_of_mem`.

    lines 68–77

    uses Subtype.ext, Finset.mem_insert_of_mem, Finset.mem_image_of_mem

              left
              have h_eq : v = two_token_kmn_lr_vertex (0 : Fin 2) b := by
                apply Subtype.ext
                exact hs
              rw [h_eq]
              apply Finset.mem_insert_of_mem
              dsimp [lr_part]
              apply Finset.mem_image_of_mem
              simp [hb]
          · -- a = 1
  7. Every mixed vertex v = {1, b} is adjacent to ll ∈ S. automation

    When a = 1, for any b ∈ Fin(n - 2), the symmetric difference of ll = {0, 1} and v = {1, b} is {0, b}, which connects 0 ∈ Fin 2 and b ∈ Fin(n - 2) and is thus an edge of K_{2, n-2}. Hence ll ∈ S is adjacent to v, verified via `aesop`.

    lines 78–87

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

            right
            refine ⟨ll, Finset.mem_insert_self _ _, ?_⟩
            refine ⟨Sum.inl (0 : Fin 2), Sum.inr b, ?_, ?_⟩
            · dsimp [completeBipartiteGraph]; left; simp
            · ext x
              simp only [Finset.mem_symmDiff, Finset.mem_insert, Finset.mem_singleton]
              rw [hs]
              dsimp [ll, two_token_kmn_ll_vertex]
              aesop
        · -- Case RR
  8. Every vertex v = {b1, b2} whose tokens both lie in Fin(n - 2) is adjacent to a vertex in S. automation

    Since b1 ≠ b2, at most one of them can equal z. If b1 = z, then b2 ≠ z, and we pick u = {0, b2} ∈ lr_part ⊆ S; the symmetric difference u Δ v is {0, b1} = {0, z}, an edge of K_{2, n-2}. If b1 ≠ z, we pick u = {0, b1} ∈ lr_part ⊆ S; then u Δ v is {0, b2}, also an edge. In each case `aesop` verifies the symmetric difference.

    lines 88–118

    uses Finset.mem_insert_of_mem, Finset.mem_image_of_mem, Finset.mem_symmDiff, Finset.mem_insert, Finset.mem_singleton

          right
          by_cases hb1 : b1 = z
          · have hb2 : b2 ≠ z := by intro h; subst h; subst hb1; exact hne rfl
            let u := two_token_kmn_lr_vertex (0 : Fin 2) b2
            have hu : u ∈ S := by
              apply Finset.mem_insert_of_mem
              dsimp [lr_part]
              apply Finset.mem_image_of_mem
              simp [hb2]
            refine ⟨u, hu, ?_⟩
            refine ⟨Sum.inl (0 : Fin 2), Sum.inr b1, ?_, ?_⟩
            · dsimp [completeBipartiteGraph]; left; simp
            · ext x
              simp only [Finset.mem_symmDiff, Finset.mem_insert, Finset.mem_singleton]
              rw [hs]
              dsimp [u, two_token_kmn_lr_vertex]
              aesop
          · let u := two_token_kmn_lr_vertex (0 : Fin 2) b1
            have hu : u ∈ S := by
              apply Finset.mem_insert_of_mem
              dsimp [lr_part]
              apply Finset.mem_image_of_mem
              simp [hb1]
            refine ⟨u, hu, ?_⟩
            refine ⟨Sum.inl (0 : Fin 2), Sum.inr b2, ?_, ?_⟩
            · dsimp [completeBipartiteGraph]; left; simp
            · ext x
              simp only [Finset.mem_symmDiff, Finset.mem_insert, Finset.mem_singleton]
              rw [hs]
              dsimp [u, two_token_kmn_lr_vertex]
              aesop
  9. The cardinality of S is at most n - 2.

    By `Finset.card_insert_le`, |S| ≤ |lr_part| + 1. By `Finset.card_image_le`, |lr_part| ≤ |Fin(n - 2) \ {z}|. By `Finset.card_erase_of_mem` and `Finset.mem_univ`, erasing z from Fin(n - 2) gives cardinality (n - 2) - 1. Combining these inequalities via linear arithmetic (`omega`) yields |S| ≤ (n - 2) - 1 + 1 = n - 2.

    lines 119–124

    uses Finset.card_insert_le, Finset.card_image_le, Finset.card_erase_of_mem, Finset.mem_univ

      · have h1 : S.card ≤ lr_part.card + 1 := Finset.card_insert_le ll lr_part
        have h2 : lr_part.card ≤ (Finset.univ.erase z).card := Finset.card_image_le
        have h3 : (Finset.univ.erase z).card = (n - 2) - 1 := by
          rw [Finset.card_erase_of_mem (Finset.mem_univ _)]
          simp
        omega
Finset.card_eq_two
A finite set has cardinality 2 if and only if it consists of two distinct elements.
Finset.pair_comm
The unordered pair {a, b} equals {b, a}.
two_token_k2_nminus2_has_dominating_set_finset_card_two_cases
Any 2-element subset of A ⊕ B is either two distinct elements of A, one element of A and one of B, or two distinct elements of B.
two_token_k2_nminus2_has_dominating_set_fin2_pair_eq
Any pair of distinct elements in Fin 2 embedded into Fin 2 ⊕ Fin k is equal to {0, 1}.
Subtype.ext
Two elements of a subtype are equal if their underlying values are equal.
Finset.mem_insert_self
An element a belongs to insert a s.
Finset.mem_insert_of_mem
If an element belongs to s, then it belongs to insert b s.
Finset.mem_image_of_mem
If a belongs to s, then f(a) belongs to Finset.image f s.
Finset.mem_symmDiff
An element belongs to the symmetric difference of two sets iff it belongs to one but not both.
Finset.mem_insert
An element belongs to insert b s iff it equals b or belongs to s.
Finset.mem_singleton
An element belongs to {a} iff it equals a.
Finset.card_insert_le
The cardinality of insert a s is at most the cardinality of s plus 1.
Finset.card_image_le
The cardinality of the image f(s) is at most the cardinality of s.
Finset.card_erase_of_mem
If an element a belongs to s, then erasing a decreases the cardinality by 1.
Finset.mem_univ
Every element of a finite type belongs to its universal finset univ.

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_k2_nminus2_has_dominating_set_finset_card_two_cases {A B : Type*} [DecidableEq A] [DecidableEq B]    (s : Finset (A ⊕ B)) (hs : s.card = 2) :    (∃ a1 a2 : A, a1 ≠ a2 ∧ s = {Sum.inl a1, Sum.inl a2}) ∨    (∃ (a : A) (b : B), s = {Sum.inl a, Sum.inr b}) ∨    (∃ b1 b2 : B, b1 ≠ b2 ∧ s = {Sum.inr b1, Sum.inr b2}) := by  rw [Finset.card_eq_two] at hs  rcases hs with ⟨x, y, hne, rfl⟩  rcases x with a1 | b1 <;> rcases y with a2 | b2  · left    refine ⟨a1, a2, ?_, rfl⟩    rintro rfl; exact hne rfl  · right; left; exact ⟨a1, b2, rfl⟩  · right; left; refine ⟨a2, b1, ?_⟩; rw [Finset.pair_comm]  · right; right    refine ⟨b1, b2, ?_, rfl⟩    rintro rfl; exact hne rfllemma two_token_k2_nminus2_has_dominating_set_fin2_pair_eq {k : ℕ} (a1 a2 : Fin 2) (hne : a1 ≠ a2) :    ({Sum.inl a1, Sum.inl a2} : Finset (Fin 2 ⊕ Fin k)) =    {Sum.inl (0 : Fin 2), Sum.inl (1 : Fin 2)} := by  revert hne  fin_cases a1 <;> fin_cases a2  · intro h; contradiction  · intro _; rfl  · intro _; rw [Finset.pair_comm]; rfl  · intro h; contradiction/-- The 2-token graph F_2(K_{2,n-2}) has a dominating set of cardinality at most n - 2. -/theorem two_token_k2_nminus2_has_dominating_set (n : ℕ) (hn : 4 ≤ n) :    ∃ S : Finset { s : Finset (Fin 2 ⊕ Fin (n - 2)) // s.card = 2 },      simple_graph_is_dominating (token_graph (completeBipartiteGraph (Fin 2) (Fin (n - 2))) 2) (S : Set _) ∧      S.card ≤ n - 2 := by  have hk : 0 < n - 2 := by omega  let z : Fin (n - 2) := ⟨0, hk⟩  let ll : { s : Finset (Fin 2 ⊕ Fin (n - 2)) // s.card = 2 } :=    two_token_kmn_ll_vertex (0 : Fin 2) (1 : Fin 2) (by decide)  let lr_part := (Finset.univ.erase z).image (fun j => two_token_kmn_lr_vertex (0 : Fin 2) j)  let S : Finset { s : Finset (Fin 2 ⊕ Fin (n - 2)) // s.card = 2 } := insert ll lr_part  refine ⟨S, ?_, ?_⟩  · intro v    rcases two_token_k2_nminus2_has_dominating_set_finset_card_two_cases v.val v.property with      (⟨a1, a2, hne, hs⟩ | ⟨a, b, hs⟩ | ⟨b1, b2, hne, hs⟩)    · -- Case LL      left      have h_eq : v = ll := by        apply Subtype.ext        dsimp [ll, two_token_kmn_ll_vertex]        rw [hs]        exact two_token_k2_nminus2_has_dominating_set_fin2_pair_eq a1 a2 hne      rw [h_eq]      exact Finset.mem_insert_self _ _    · -- Case LR      fin_cases a      · -- a = 0        by_cases hb : b = z        · -- b = z          subst hb          right          refine ⟨ll, Finset.mem_insert_self _ _, ?_⟩          refine ⟨Sum.inl (1 : Fin 2), Sum.inr z, ?_, ?_⟩          · dsimp [completeBipartiteGraph]; left; simp          · ext x            simp only [Finset.mem_symmDiff, Finset.mem_insert, Finset.mem_singleton]            rw [hs]            dsimp [ll, two_token_kmn_ll_vertex]            aesop        · -- b ≠ z          left          have h_eq : v = two_token_kmn_lr_vertex (0 : Fin 2) b := by            apply Subtype.ext            exact hs          rw [h_eq]          apply Finset.mem_insert_of_mem          dsimp [lr_part]          apply Finset.mem_image_of_mem          simp [hb]      · -- a = 1        right        refine ⟨ll, Finset.mem_insert_self _ _, ?_⟩        refine ⟨Sum.inl (0 : Fin 2), Sum.inr b, ?_, ?_⟩        · dsimp [completeBipartiteGraph]; left; simp        · ext x          simp only [Finset.mem_symmDiff, Finset.mem_insert, Finset.mem_singleton]          rw [hs]          dsimp [ll, two_token_kmn_ll_vertex]          aesop    · -- Case RR      right      by_cases hb1 : b1 = z      · have hb2 : b2 ≠ z := by intro h; subst h; subst hb1; exact hne rfl        let u := two_token_kmn_lr_vertex (0 : Fin 2) b2        have hu : u ∈ S := by          apply Finset.mem_insert_of_mem          dsimp [lr_part]          apply Finset.mem_image_of_mem          simp [hb2]        refine ⟨u, hu, ?_⟩        refine ⟨Sum.inl (0 : Fin 2), Sum.inr b1, ?_, ?_⟩        · dsimp [completeBipartiteGraph]; left; simp        · ext x          simp only [Finset.mem_symmDiff, Finset.mem_insert, Finset.mem_singleton]          rw [hs]          dsimp [u, two_token_kmn_lr_vertex]          aesop      · let u := two_token_kmn_lr_vertex (0 : Fin 2) b1        have hu : u ∈ S := by          apply Finset.mem_insert_of_mem          dsimp [lr_part]          apply Finset.mem_image_of_mem          simp [hb1]        refine ⟨u, hu, ?_⟩        refine ⟨Sum.inl (0 : Fin 2), Sum.inr b2, ?_, ?_⟩        · dsimp [completeBipartiteGraph]; left; simp        · ext x          simp only [Finset.mem_symmDiff, Finset.mem_insert, Finset.mem_singleton]          rw [hs]          dsimp [u, two_token_kmn_lr_vertex]          aesop  · have h1 : S.card ≤ lr_part.card + 1 := Finset.card_insert_le ll lr_part    have h2 : lr_part.card ≤ (Finset.univ.erase z).card := Finset.card_image_le    have h3 : (Finset.univ.erase z).card = (n - 2) - 1 := by      rw [Finset.card_erase_of_mem (Finset.mem_univ _)]      simp    omega
See it in the graphDiscuss this resultChallenge it