AFTD Auto-Formalizing Theoretical Domains

wild_rainbow_equal_blocks_closed_matching_crosses

theoremverified

In a properly colored complete graph with one specified missing vertex for each color, let two disjoint equally sized blocks have no common internal color except i0. If a different color i closes their union, every color-i partner of a vertex in the first block belongs to the second block.

Statement

theorem wild_rainbow_equal_blocks_closed_matching_crosses
    {n k : ℕ}
    (c : (⊤ : SimpleGraph (Fin n)).lineGraph.Coloring (Fin k))
    (m : Fin k → Fin n)
    (hm : ∀ i v, (∀ w (h : v ≠ w), c ⟨s(v,w),wild_kn_mem h⟩ ≠ i) ↔ v = m i)
    (A B : Finset (Fin n)) (hdis : Disjoint A B) (hcard : A.card = B.card)
    (i0 i : Fin k) (hne : i ≠ i0)
    (hsep : ∀ a ∈ A, ∀ a' ∈ A, ∀ ha : a ≠ a',
      ∀ b ∈ B, ∀ b' ∈ B, ∀ hb : b ≠ b',
        c ⟨s(a,a'),wild_kn_mem ha⟩ = c ⟨s(b,b'),wild_kn_mem hb⟩ →
          c ⟨s(a,a'),wild_kn_mem ha⟩ = i0)
    (hclosed : w279_closed c i (A ∪ B)) :
    ∀ a ∈ A, w279_pc c i a ∈ B
Source
IN-338 structural/repair helpers for OP-306, the prescribed-coloring conjecture in arXiv:2610.22142 Sections3.3.2 and6. Exact matching-involution balance and the method obstruction computed in experiment8464. These are certificate/method lemmas, not new wild-number bounds or research advances.
Verified
05 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3

The proof, explained

The theorem is proved by contradiction. First, the missing vertex m(i) of color i cannot lie in A ∪ B, because |A ∪ B| = 2|A| is even, whereas a closed set containing m(i) must have odd cardinality. Thus the color-i partner operation p is a fixed-point-free involution on A ∪ B, which by an equicardinal block counting lemma implies that the number of internal color-i pairs in A equals the number in B. If some a ∈ A had its partner outside B, it would fall in A, forcing an internal color-i pair in B as well; but by hypothesis, the only internal color shared by A and B is i0, contradicting i ≠ i0.

  1. Enable classical reasoning and define p as the color-i partner function.

    We work classically and define p(v) = w279_pc c i v, which assigns to each vertex v its partner along the incident edge of color i.

    lines 17–18

      classical
      let p := w279_pc c i
  2. The missing vertex m(i) of color i does not belong to A ∪ B.

    Suppose for contradiction that m(i) ∈ A ∪ B. Since A and B are disjoint with equal cardinality, |A ∪ B| = |A| + |B| = 2|A| is even. However, because A ∪ B is closed under color i, the formula from `w279_card_closed` implies |A ∪ B| = 2k + 1 (since m(i) ∈ A ∪ B gives 1 via `if_pos`), which is odd. Linear integer arithmetic (`omega`) detects the impossibility of an even integer equaling an odd integer and derives False.

    lines 19–23

    uses w279_card_closed, if_pos, card_union_of_disjoint

      have hmiss : m i ∉ A ∪ B := by
        intro hmi
        have hh := w279_card_closed c m hm i (A ∪ B) hclosed
        rw [if_pos hmi, card_union_of_disjoint hdis] at hh
        omega
  3. No vertex in A ∪ B equals the missing vertex m(i).

    If some vertex v ∈ A ∪ B satisfied v = m(i), then m(i) would belong to A ∪ B, directly contradicting the previous step.

    lines 24–26

      have hvne : ∀ v ∈ A ∪ B, v ≠ m i := by
        intro v hv he
        exact hmiss (he ▸ hv)
  4. The partner map p preserves A ∪ B.

    By `w279_closed_iff`, a set is closed under color i if and only if every element different from m(i) has its color-i partner in the set. Since A ∪ B is closed and contains no vertex equal to m(i), p(v) ∈ A ∪ B for every v ∈ A ∪ B.

    lines 27–29

    uses w279_closed_iff

      have hstable : ∀ v ∈ A ∪ B, p v ∈ A ∪ B := by
        intro v hv
        exact (w279_closed_iff c m hm i (A ∪ B)).mp hclosed v hv (hvne v hv)
  5. On A ∪ B, the map p is an involution: p(p(v)) = v for all v ∈ A ∪ B.

    Because no vertex v in A ∪ B is the missing vertex m(i), each such vertex is paired along a color-i edge with p(v), and iterating the partner map returns the original vertex v by `w279_pc_pc`.

    lines 30–32

    uses w279_pc_pc

      have hinv : ∀ v ∈ A ∪ B, p (p v) = v := by
        intro v hv
        exact w279_pc_pc c m hm i v (hvne v hv)
  6. The number of vertices in A whose color-i partner lies in A equals the number of vertices in B whose color-i partner lies in B.

    Since A and B are disjoint sets of equal size and p is an involution on A ∪ B preserving A ∪ B, the lemma `involution_equal_blocks_internal_card` applies directly to equate the counts of internal pairs in A and in B.

    line 33

    uses involution_equal_blocks_internal_card

      have heq := involution_equal_blocks_internal_card p A B hdis hcard hstable hinv
  7. If some vertex a ∈ A had its partner outside B (so p(a) ∈ A), then there would also exist a vertex in B whose partner is in B.

    Assume for contradiction that p(a) ∉ B for some a ∈ A. Since p(a) ∈ A ∪ B, this forces p(a) ∈ A. Thus the set of vertices in A mapped into A contains a, so its cardinality is strictly positive. By the equality of internal counts between A and B, the set of vertices in B mapped into B also has strictly positive cardinality (`omega`).

    lines 34–38

    uses mem_union, mem_union_left, card_pos, mem_filter

      intro a ha
      by_contra hpB
      have hpA : p a ∈ A := (mem_union.mp (hstable a (mem_union_left B ha))).resolve_right hpB
      have hposA : 0 < (A.filter fun v => p v ∈ A).card := card_pos.mpr ⟨a,mem_filter.mpr ⟨ha,hpA⟩⟩
      have hposB : 0 < (B.filter fun v => p v ∈ B).card := by omega
  8. The existence of internal color-i pairs in both A and B contradicts i ≠ i0, completing the proof.

    Because the set of internal partners in B is nonempty, choose a vertex b ∈ B with p(b) ∈ B. By `w279_pc_spec`, the edge between a and p(a) has color i, and the edge between b and p(b) has color i. Both are internal edges in A and B respectively. By the block separation hypothesis `hsep`, any color shared by an internal edge in A and an internal edge in B must be i0, so i = i0. This contradicts the hypothesis i ≠ i0 (`hne`).

    lines 39–44

    uses card_pos, mem_filter, w279_pc_spec, mem_union_left, mem_union_right

      obtain ⟨b,hb⟩ := card_pos.mp hposB
      obtain ⟨hbB,hpB'⟩ := mem_filter.mp hb
      obtain ⟨hane,hac⟩ := w279_pc_spec c m hm i a (hvne a (mem_union_left B ha))
      obtain ⟨hbne,hbc⟩ := w279_pc_spec c m hm i b (hvne b (mem_union_right A hbB))
      have hci0 := hsep a ha (p a) hpA hane b hbB (p b) hpB' hbne (hac.trans hbc.symm)
      exact hne (hac.symm.trans hci0)
card_union_of_disjoint
The cardinality of the union of two disjoint finite sets is the sum of their cardinalities.
card_pos
A finite set has cardinality strictly greater than zero if and only if it contains at least one element.
if_pos
If a condition holds, an if-then-else expression evaluates to its 'then' branch.
involution_equal_blocks_internal_card
For any involution on the union of two disjoint sets of equal cardinality that maps the union to itself, the number of elements in the first set mapped into itself equals the number of elements in the second set mapped into itself.
mem_filter
An element belongs to a filtered set {x ∈ s | P x} if and only if it belongs to s and satisfies the predicate P.
mem_union
An element belongs to the union of two sets if and only if it belongs to at least one of them.
mem_union_left
An element belonging to a set s also belongs to s ∪ t.
mem_union_right
An element belonging to a set t also belongs to s ∪ t.
w279_card_closed
For a set U closed under color i, the cardinality of U equals 2k + 1 if the missing vertex m(i) is in U, and 2k if it is not.
w279_closed_iff
A set U is closed under color i if and only if for every u ∈ U with u ≠ m(i), the color-i partner of u also lies in U.
w279_pc_pc
For any vertex v ≠ m(i), applying the color-i partner operation twice returns v.
w279_pc_spec
For any vertex v ≠ m(i), v is distinct from its color-i partner w279_pc c i v, and the edge connecting them has color i.

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 Finsetset_option maxHeartbeats 2500000theorem wild_rainbow_equal_blocks_closed_matching_crosses    {n k : ℕ}    (c : (⊤ : SimpleGraph (Fin n)).lineGraph.Coloring (Fin k))    (m : Fin k → Fin n)    (hm : ∀ i v, (∀ w (h : v ≠ w), c ⟨s(v,w),wild_kn_mem h⟩ ≠ i) ↔ v = m i)    (A B : Finset (Fin n)) (hdis : Disjoint A B) (hcard : A.card = B.card)    (i0 i : Fin k) (hne : i ≠ i0)    (hsep : ∀ a ∈ A, ∀ a' ∈ A, ∀ ha : a ≠ a',      ∀ b ∈ B, ∀ b' ∈ B, ∀ hb : b ≠ b',        c ⟨s(a,a'),wild_kn_mem ha⟩ = c ⟨s(b,b'),wild_kn_mem hb⟩ →          c ⟨s(a,a'),wild_kn_mem ha⟩ = i0)    (hclosed : w279_closed c i (A ∪ B)) :    ∀ a ∈ A, w279_pc c i a ∈ B := by  classical  let p := w279_pc c i  have hmiss : m i ∉ A ∪ B := by    intro hmi    have hh := w279_card_closed c m hm i (A ∪ B) hclosed    rw [if_pos hmi, card_union_of_disjoint hdis] at hh    omega  have hvne : ∀ v ∈ A ∪ B, v ≠ m i := by    intro v hv he    exact hmiss (he ▸ hv)  have hstable : ∀ v ∈ A ∪ B, p v ∈ A ∪ B := by    intro v hv    exact (w279_closed_iff c m hm i (A ∪ B)).mp hclosed v hv (hvne v hv)  have hinv : ∀ v ∈ A ∪ B, p (p v) = v := by    intro v hv    exact w279_pc_pc c m hm i v (hvne v hv)  have heq := involution_equal_blocks_internal_card p A B hdis hcard hstable hinv  intro a ha  by_contra hpB  have hpA : p a ∈ A := (mem_union.mp (hstable a (mem_union_left B ha))).resolve_right hpB  have hposA : 0 < (A.filter fun v => p v ∈ A).card := card_pos.mpr ⟨a,mem_filter.mpr ⟨ha,hpA⟩⟩  have hposB : 0 < (B.filter fun v => p v ∈ B).card := by omega  obtain ⟨b,hb⟩ := card_pos.mp hposB  obtain ⟨hbB,hpB'⟩ := mem_filter.mp hb  obtain ⟨hane,hac⟩ := w279_pc_spec c m hm i a (hvne a (mem_union_left B ha))  obtain ⟨hbne,hbc⟩ := w279_pc_spec c m hm i b (hvne b (mem_union_right A hbB))  have hci0 := hsep a ha (p a) hpA hane b hbB (p b) hpB' hbne (hac.trans hbc.symm)  exact hne (hac.symm.trans hci0)
See it in the graphDiscuss this resultChallenge it