three_token_k2n_assemble_three_layers
If the explicit candidate family has the claimed cardinality and dominates each of the layers with zero, one and two left-part tokens, the required dominating set exists.
Statement
theorem three_token_k2n_assemble_three_layers (n : ℕ) (hn : 4 ≤ n)
(hcard : (three_token_k2n_explicit_family n hn).card ≤ (n / 2).choose 2 + (n - n / 2).choose 2 + n - 2)
(h0 : ∀ z : {s : Finset (Fin 2 ⊕ Fin n) // s.card = 3}, three_token_k2n_left_count z = 0 →
z ∈ three_token_k2n_explicit_family n hn ∨ ∃ w ∈ three_token_k2n_explicit_family n hn,
(token_graph (completeBipartiteGraph (Fin 2) (Fin n)) 3).Adj w z)
(h1 : ∀ z : {s : Finset (Fin 2 ⊕ Fin n) // s.card = 3}, three_token_k2n_left_count z = 1 →
z ∈ three_token_k2n_explicit_family n hn ∨ ∃ w ∈ three_token_k2n_explicit_family n hn,
(token_graph (completeBipartiteGraph (Fin 2) (Fin n)) 3).Adj w z)
(h2 : ∀ z : {s : Finset (Fin 2 ⊕ Fin n) // s.card = 3}, three_token_k2n_left_count z = 2 →
z ∈ three_token_k2n_explicit_family n hn ∨ ∃ w ∈ three_token_k2n_explicit_family n hn,
(token_graph (completeBipartiteGraph (Fin 2) (Fin n)) 3).Adj w z) :
∃ S : Finset {s : Finset (Fin 2 ⊕ Fin n) // s.card = 3},
simple_graph_is_dominating (token_graph (completeBipartiteGraph (Fin 2) (Fin n)) 3) (S : Set _) ∧
S.card ≤ (n / 2).choose 2 + (n - n / 2).choose 2 + n - 2- Source
- Explicit construction for three_token_k2n_has_dominating_set and OP-666.
- Verified
- 02 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- three_token_k2n_explicit_familyThe candidate family of three-token configurations: all configurations with left vertex 0 and a same-half pair on the right, the…
- three_token_k2n_left_countThe number of left-part vertices in a three-token configuration.
- three_token_k2n_assemble_layer_coverIf the explicit candidate family has the claimed cardinality and dominates every configuration in each of the three possible left-token…
- 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.
The proof, explained
The proof reduces the existence of the desired dominating set to verifying that the explicit candidate family dominates every 3-token configuration having at most two tokens on the left part of $K_{2, n}$, using the assembly lemma `three_token_k2n_assemble_layer_cover`. Since the left-token count $k \le 2$ can only be 0, 1, or 2, an exhaustive case analysis on $k$ dispatches each case immediately using the supplied layer hypotheses $h0$, $h1$, and $h2$.
To obtain the required dominating set, it suffices to show that the explicit family dominates every 3-token configuration with at most two left-part tokens.
Applying `three_token_k2n_assemble_layer_cover` with the size hypothesis (hcard) reduces the existence of the desired dominating set to showing that any vertex $z$ whose left-part token count $k$ satisfies $k \le 2$ is either in the candidate family or adjacent to a member of it.
uses
three_token_k2n_assemble_layer_coverapply three_token_k2n_assemble_layer_cover n hn hcardEvery 3-token configuration with at most two left-part tokens is dominated by the explicit candidate family.
Given an arbitrary vertex $z$ whose left-part token count is $k$ with $k \le 2$, the only possible values for $k$ are 0, 1, and 2. Performing this case analysis (`interval_cases k`) yields three subgoals, which are directly discharged by the respective layer domination hypotheses $h0$, $h1$, and $h2$.
intro k hk z hz interval_cases k · exact h0 z hz · exact h1 z hz · exact h2 z hz
three_token_k2n_assemble_layer_cover- If the explicit candidate family of 3-tokens on $K_{2, n}$ satisfies the cardinality bound and dominates every 3-token configuration with at most two left-part tokens, then there exists a dominating set of the 3-token graph on $K_{2, n}$ satisfying the cardinality bound $\binom{\lfloor n/2 \rfloor}{2} + \binom{n - \lfloor n/2 \rfloor}{2} + n - 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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
theorem three_token_k2n_assemble_three_layers (n : ℕ) (hn : 4 ≤ n) (hcard : (three_token_k2n_explicit_family n hn).card ≤ (n / 2).choose 2 + (n - n / 2).choose 2 + n - 2) (h0 : ∀ z : {s : Finset (Fin 2 ⊕ Fin n) // s.card = 3}, three_token_k2n_left_count z = 0 → z ∈ three_token_k2n_explicit_family n hn ∨ ∃ w ∈ three_token_k2n_explicit_family n hn, (token_graph (completeBipartiteGraph (Fin 2) (Fin n)) 3).Adj w z) (h1 : ∀ z : {s : Finset (Fin 2 ⊕ Fin n) // s.card = 3}, three_token_k2n_left_count z = 1 → z ∈ three_token_k2n_explicit_family n hn ∨ ∃ w ∈ three_token_k2n_explicit_family n hn, (token_graph (completeBipartiteGraph (Fin 2) (Fin n)) 3).Adj w z) (h2 : ∀ z : {s : Finset (Fin 2 ⊕ Fin n) // s.card = 3}, three_token_k2n_left_count z = 2 → z ∈ three_token_k2n_explicit_family n hn ∨ ∃ w ∈ three_token_k2n_explicit_family n hn, (token_graph (completeBipartiteGraph (Fin 2) (Fin n)) 3).Adj w z) : ∃ S : Finset {s : Finset (Fin 2 ⊕ Fin n) // s.card = 3}, simple_graph_is_dominating (token_graph (completeBipartiteGraph (Fin 2) (Fin n)) 3) (S : Set _) ∧ S.card ≤ (n / 2).choose 2 + (n - n / 2).choose 2 + n - 2 := by apply three_token_k2n_assemble_layer_cover n hn hcard intro k hk z hz interval_cases k · exact h0 z hz · exact h1 z hz · exact h2 z hz