AFTD Auto-Formalizing Theoretical Domains

wild_closed_cut_swap_color_invariant

theoremverified

Swapping the endpoints of a color-i edge in a proper complete-graph edge coloring preserves whether each vertex cut is closed for color i.

Statement

theorem wild_closed_cut_swap_color_invariant {n k : ℕ}
    (c : (⊤ : SimpleGraph (Fin n)).lineGraph.Coloring (Fin k))
    (i : Fin k) (U : Finset (Fin n)) (a b : Fin n) (hab : a ≠ b)
    (hc : c ⟨s(a,b),wild_kn_mem hab⟩ = i) :
    w279_closed c i (U.image (Equiv.swap a b)) ↔ w279_closed c i U
Source
Helper for the structural exchange route in the OP-306 campaign on arXiv:2610.22142. This records a cut obstruction or a sufficient test for exchanges, not a new wild-number bound.
Verified
29 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3

The proof, explained

The proof relies on the key observation that any color-i closed vertex set V is invariant under the transposition τ = (a b) of the endpoints of a color-i edge: closure requires that either both endpoints belong to V or neither does, while all other vertices are fixed by τ. Applying this invariance to U directly proves the reverse direction, and applying it to τ(U)—combined with the fact that transpositions are involutions—proves the forward direction.

  1. For any color-i closed set V, the vertex a belongs to V if and only if b belongs to V.

    To show that any color-i closed set V is invariant under swapping a and b, we first establish that a ∈ V ↔ b ∈ V. If a ∈ V, then since the edge {a, b} has color i, the closure of V forces b ∈ V. Conversely, by the symmetry of edge coloring (w279_c_swap), the edge {b, a} also has color i, so if b ∈ V, then a ∈ V.

    lines 9–13

    uses Ne.symm, w279_c_swap

      have fixed : ∀ (V : Finset (Fin n)), w279_closed c i V → V.image (Equiv.swap a b) = V := by
        intro V hV
        have hm : a ∈ V ↔ b ∈ V :=
          ⟨fun ha => hV a ha b hab hc,
           fun hb => hV b hb a (Ne.symm hab) ((w279_c_swap c (Ne.symm hab)).trans hc)⟩
  2. Any color-i closed set V is invariant under swapping a and b: τ(V) = V.

    By set extensionality, we check that v ∈ τ(V) ↔ v ∈ V for every vertex v. By wild_swap_mem_image, this is equivalent to τ(v) ∈ V ↔ v ∈ V. We case split on v: if v = a, τ(a) = b (Equiv.swap_apply_left) and the claim reduces to b ∈ V ↔ a ∈ V; if v = b, τ(b) = a (Equiv.swap_apply_right) and it reduces to a ∈ V ↔ b ∈ V; and if v is neither a nor b, the swap fixes v (Equiv.swap_apply_of_ne_of_ne), so τ(v) = v and the equivalence holds trivially.

    lines 14–20

    uses wild_swap_mem_image, Equiv.swap_apply_left, Equiv.swap_apply_right, Equiv.swap_apply_of_ne_of_ne

        ext v
        rw [wild_swap_mem_image]
        by_cases hva : v = a
        · subst v; simpa only [Equiv.swap_apply_left] using hm.symm
        by_cases hvb : v = b
        · subst v; simpa only [Equiv.swap_apply_right] using hm
        rw [Equiv.swap_apply_of_ne_of_ne hva hvb]
  3. If the swapped set τ(U) is closed for color i, then U is closed for color i.

    We split the equivalence into both directions (constructor). For the forward direction, suppose τ(U) is closed for color i. Applying the invariance lemma to V = τ(U) shows that τ(τ(U)) = τ(U). Since transpositions are involutions (Equiv.swap_apply_self, using wild_swap_mem_image), swapping twice yields τ(τ(U)) = U. Substituting this into the invariance identity gives U = τ(U), so the assumption that τ(U) is closed immediately implies that U is closed.

    lines 21–28

    uses wild_swap_mem_image, Equiv.swap_apply_self

      constructor
      · intro h
        have hf := fixed (U.image (Equiv.swap a b)) h
        have hh : (U.image (Equiv.swap a b)).image (Equiv.swap a b) = U := by
          ext v
          simp only [wild_swap_mem_image, Equiv.swap_apply_self]
        rw [hh] at hf
        simpa only [← hf] using h
  4. If U is closed for color i, then τ(U) is closed for color i.

    For the reverse direction, suppose U is closed for color i. Applying the invariance lemma to U yields τ(U) = U. Rewriting τ(U) to U transforms the goal into the hypothesis that U is closed, which is already known.

    lines 29–31

      · intro h
        rw [fixed U h]
        exact h
Ne.symm
Inequality is symmetric: if a ≠ b, then b ≠ a.
w279_c_swap
In an edge coloring of a complete graph, the edge connecting u to v has the same color as the edge connecting v to u.
wild_swap_mem_image
An element v belongs to the image of a set U under the transposition of a and b if and only if the transposition applied to v belongs to U.
Equiv.swap_apply_left
The transposition of a and b maps a to b.
Equiv.swap_apply_right
The transposition of a and b maps b to a.
Equiv.swap_apply_of_ne_of_ne
The transposition of a and b fixes every element distinct from both a and b.
Equiv.swap_apply_self
Applying the transposition of a and b twice to any element yields the element itself.

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 Classicalset_option maxHeartbeats 1000000theorem wild_closed_cut_swap_color_invariant {n k : ℕ}    (c : (⊤ : SimpleGraph (Fin n)).lineGraph.Coloring (Fin k))    (i : Fin k) (U : Finset (Fin n)) (a b : Fin n) (hab : a ≠ b)    (hc : c ⟨s(a,b),wild_kn_mem hab⟩ = i) :    w279_closed c i (U.image (Equiv.swap a b)) ↔ w279_closed c i U := by  have fixed : ∀ (V : Finset (Fin n)), w279_closed c i V → V.image (Equiv.swap a b) = V := by    intro V hV    have hm : a ∈ V ↔ b ∈ V :=      ⟨fun ha => hV a ha b hab hc,       fun hb => hV b hb a (Ne.symm hab) ((w279_c_swap c (Ne.symm hab)).trans hc)⟩    ext v    rw [wild_swap_mem_image]    by_cases hva : v = a    · subst v; simpa only [Equiv.swap_apply_left] using hm.symm    by_cases hvb : v = b    · subst v; simpa only [Equiv.swap_apply_right] using hm    rw [Equiv.swap_apply_of_ne_of_ne hva hvb]  constructor  · intro h    have hf := fixed (U.image (Equiv.swap a b)) h    have hh : (U.image (Equiv.swap a b)).image (Equiv.swap a b) = U := by      ext v      simp only [wild_swap_mem_image, Equiv.swap_apply_self]    rw [hh] at hf    simpa only [← hf] using h  · intro h    rw [fixed U h]    exact h
See it in the graphDiscuss this resultChallenge it