AFTD Auto-Formalizing Theoretical Domains

wild_closed_cut_swap_crossing_incident

theoremverified

For any proper edge coloring of a complete graph, if swapping vertices a and b in a vertex cut U makes U closed for color i, every old color-i edge crossing U has an endpoint among a and b.

Statement

theorem wild_closed_cut_swap_crossing_incident {n k : ℕ}
    (c : (⊤ : SimpleGraph (Fin n)).lineGraph.Coloring (Fin k))
    (i : Fin k) (U : Finset (Fin n)) (a b : Fin n)
    (hclosed : w279_closed c i (U.image (Equiv.swap a b)))
    (u v : Fin n) (huv : u ≠ v) (hu : u ∈ U) (hv : v ∉ U)
    (hc : c ⟨s(u,v),wild_kn_mem huv⟩ = i) :
    u = a ∨ u = b ∨ v = a ∨ v = b
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 2
Used by 2
  • wild_closed_cut_swap_crossing_card_le_twoFor any proper edge coloring of a complete graph, if the image of a vertex cut U under a transposition is closed for color i, at most two…
  • wild_closed_cut_swap_iffLet a belong to U and b lie outside U. In any proper complete-graph edge coloring, the swapped cut is closed for i exactly when a has no…

The proof, explained

Proof by contradiction: if neither endpoint u nor v of the crossing color-i edge is a or b, then swapping a and b leaves both vertices fixed. Hence u is in the swapped cut and the edge {u, v} still has color i, forcing v to belong to the swapped cut by closure. Since the swap fixes v and is injective, this implies v was in the original cut U, contradicting that the edge crossed U.

  1. Assume for contradiction that neither u nor v is a or b.

    Assume the negation of the conclusion.

    line 11

      by_contra! h
  2. Both u and v are fixed by the transposition, so u is in the swapped set.

    Since u and v differ from a and b, swapping a and b leaves them unchanged. In particular, u is in the image of U under the swap.

    lines 12–14

    uses Equiv.swap_apply_of_ne_of_ne, Finset.mem_image.2

      have hsu : Equiv.swap a b u = u := Equiv.swap_apply_of_ne_of_ne h.1 h.2.1
      have hsv : Equiv.swap a b v = v := Equiv.swap_apply_of_ne_of_ne h.2.2.1 h.2.2.2
      have hu' : u ∈ U.image (Equiv.swap a b) := Finset.mem_image.2 ⟨u,hu,hsu⟩
  3. By closure of the swapped set under color i, v must also belong to the swapped set.

    Applying the hypothesis that the swapped set is closed under color i to the color-i edge between u and v shows that v is in the swapped set.

    line 15

      have hv' := hclosed u hu' v huv hc
  4. The preimage of v under the swap is v itself, placing v in U, a contradiction.

    Since v is in the image of U, some w in U maps to v. But the swap also maps v to v, and permutations are injective, so w = v, which contradicts v not in U.

    lines 16–18

    uses Finset.mem_image.1

      obtain ⟨w,hw,he⟩ := Finset.mem_image.1 hv'
      have hwv : w = v := (Equiv.swap a b).injective (he.trans hsv.symm)
      exact hv (hwv ▸ hw)
Equiv.swap_apply_of_ne_of_ne
Swapping two elements fixes any element distinct from both.

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_crossing_incident {n k : ℕ}    (c : (⊤ : SimpleGraph (Fin n)).lineGraph.Coloring (Fin k))    (i : Fin k) (U : Finset (Fin n)) (a b : Fin n)    (hclosed : w279_closed c i (U.image (Equiv.swap a b)))    (u v : Fin n) (huv : u ≠ v) (hu : u ∈ U) (hv : v ∉ U)    (hc : c ⟨s(u,v),wild_kn_mem huv⟩ = i) :    u = a ∨ u = b ∨ v = a ∨ v = b := by  by_contra! h  have hsu : Equiv.swap a b u = u := Equiv.swap_apply_of_ne_of_ne h.1 h.2.1  have hsv : Equiv.swap a b v = v := Equiv.swap_apply_of_ne_of_ne h.2.2.1 h.2.2.2  have hu' : u ∈ U.image (Equiv.swap a b) := Finset.mem_image.2 ⟨u,hu,hsu⟩  have hv' := hclosed u hu' v huv hc  obtain ⟨w,hw,he⟩ := Finset.mem_image.1 hv'  have hwv : w = v := (Equiv.swap a b).injective (he.trans hsv.symm)  exact hv (hwv ▸ hw)
See it in the graphDiscuss this resultChallenge it