AFTD Auto-Formalizing Theoretical Domains

two_token_domination_number_ge_ceil_half

theoremverifiedformalization

Let 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) is at least (Fintype.card V + 1) / 2.

Statement

theorem two_token_domination_number_ge_ceil_half {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) (hγ : 2 ≤ simple_graph_domination_number G) :
    (Fintype.card V + 1) / 2 ≤ simple_graph_domination_number (token_graph G 2)
Formalizes
arXiv:2611.15124, Theorem 1.3
Verified
14 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • two_token_dominating_set_card_ge_ceil_halfLet 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)…
  • simple_graph_is_dominatingA subset S of vertices in a simple graph G is a dominating set if every vertex of G is in S or is adjacent to a vertex in S.
  • token_graphThe k-token graph F_k(G) of a simple graph G has as vertices the k-subsets of V(G), with two k-subsets adjacent whenever their symmetric…
  • simple_graph_domination_numberThe domination number gamma(G) of a finite simple graph G is the minimum cardinality of a dominating set of G.
Used by 1
  • two_token_domination_number_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 every finite type $V$ with decidable equality and every simple graph $G$ on $V$, if the domination number of $G$ is at least 2, then the domination number of the 2-token graph of $G$ is at least $\lceil |V| / 2 \rceil$ (expressed as $(|V| + 1) / 2$ using natural number integer 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

By definition, the domination number of the 2-token graph F_2(G) is the infimum of the cardinalities of its dominating sets. Because dominating sets exist (for instance, the universal set of all vertices), this infimum is achieved by some dominating set S. The result then follows from `two_token_dominating_set_card_ge_ceil_half`, which establishes that any dominating set of F_2(G) must have size at least (|V| + 1) / 2 whenever the domination number of G is at least 2.

  1. The domination number of F_2(G) is expressed as the infimum of the cardinalities of all dominating sets of F_2(G).

    We unfold the definition of `simple_graph_domination_number`, transforming the goal into showing that (|V| + 1) / 2 is at most the infimum of the set of sizes of dominating sets of the 2-token graph F_2(G).

    line 5

      unfold simple_graph_domination_number
  2. The set of cardinalities of dominating sets of F_2(G) is nonempty.

    Dominating sets exist in F_2(G): taking the universal set of all vertices of F_2(G) (`Finset.univ`), every vertex v trivially belongs to it, so `Finset.univ` is dominating. Its cardinality witnesses that the set of sizes of dominating sets is nonempty.

    lines 6–12

      have hne : {k | ∃ S : Finset { s : Finset V // s.card = 2 },
          simple_graph_is_dominating (token_graph G 2) ↑S ∧ S.card = k}.Nonempty := by
        use (Finset.univ : Finset { s : Finset V // s.card = 2 }).card
        refine ⟨Finset.univ, ?_, rfl⟩
        intro v
        left
        simp
  3. There exists a dominating set S of F_2(G) whose cardinality attains the domination number of F_2(G).

    Because the set of sizes of dominating sets is a nonempty set of natural numbers, `Nat.sInf_mem` guarantees that its infimum belongs to the set. Unpacking this condition provides a dominating set S whose size equals this infimum (the domination number).

    lines 13–15

    uses Nat.sInf_mem

      have hmem := Nat.sInf_mem hne
      dsimp at hmem
      rcases hmem with ⟨S, hdom, hcard⟩
  4. The domination number of F_2(G) is at least (|V| + 1) / 2.

    Replacing the infimum with the cardinality of S, the goal reduces to showing (|V| + 1) / 2 ≤ |S|. This inequality is precisely the conclusion of `two_token_dominating_set_card_ge_ceil_half`, applied to G, the hypothesis that G has domination number at least 2, and the dominating set S.

    lines 16–17

    uses two_token_dominating_set_card_ge_ceil_half

      rw [← hcard]
      exact two_token_dominating_set_card_ge_ceil_half G hγ S hdom
Nat.sInf_mem
A nonempty set of natural numbers contains its infimum (its minimum element).
two_token_dominating_set_card_ge_ceil_half
In a finite simple graph G with domination number at least 2, every dominating set of the 2-token graph F_2(G) has cardinality at least (|V| + 1) / 2.

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

/-- The domination number of F_2(G) is at least ceil(n/2) when G has domination number at least 2. -/theorem two_token_domination_number_ge_ceil_half {V : Type*} [Fintype V] [DecidableEq V]    (G : SimpleGraph V) (hγ : 2 ≤ simple_graph_domination_number G) :    (Fintype.card V + 1) / 2 ≤ simple_graph_domination_number (token_graph G 2) := by  unfold simple_graph_domination_number  have hne : {k | ∃ S : Finset { s : Finset V // s.card = 2 },      simple_graph_is_dominating (token_graph G 2) ↑S ∧ S.card = k}.Nonempty := by    use (Finset.univ : Finset { s : Finset V // s.card = 2 }).card    refine ⟨Finset.univ, ?_, rfl⟩    intro v    left    simp  have hmem := Nat.sInf_mem hne  dsimp at hmem  rcases hmem with ⟨S, hdom, hcard⟩  rw [← hcard]  exact two_token_dominating_set_card_ge_ceil_half G hγ S hdom
See it in the graphDiscuss this resultChallenge it