AFTD Auto-Formalizing Theoretical Domains

wild_closed_cut_swap_iff

theoremverified

Let 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 i-neighbor in U, b has no i-neighbor outside U, ab is not colored i, and every old crossing i-edge has its U-end a or its other end b.

Statement

theorem wild_closed_cut_swap_iff {n k : ℕ}
    (c : (⊤ : SimpleGraph (Fin n)).lineGraph.Coloring (Fin k))
    (i : Fin k) (U : Finset (Fin n)) (a b : Fin n)
    (ha : a ∈ U) (hb : b ∉ U) :
    w279_closed c i (U.image (Equiv.swap a b)) ↔
      (∀ w ∈ U, ∀ h : a ≠ w, c ⟨s(a,w),wild_kn_mem h⟩ ≠ i) ∧
      (∀ w ∉ U, ∀ h : b ≠ w, c ⟨s(b,w),wild_kn_mem h⟩ ≠ i) ∧
      (∀ h : a ≠ b, c ⟨s(a,b),wild_kn_mem h⟩ ≠ i) ∧
      (∀ u ∈ U, ∀ v ∉ U, ∀ h : u ≠ v,
        c ⟨s(u,v),wild_kn_mem h⟩ = i → u = 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 3
Used by 1

The proof, explained

The swapped cut U' = (U \ {a}) ∪ {b} is closed under color i if and only if no edge of color i crosses between U' and (U')ᶜ. In the forward direction, assuming closure of U', any i-neighbor of a in U, any i-neighbor of b outside U, or an i-colored edge ab would immediately pull an outside vertex into U' or an inside vertex out of U'; moreover, existing crossing i-edges can only survive across the swap if their endpoints are a or b. In the reverse direction, assuming the four conditions, whenever u ∈ U' is incident to an i-edge uv, a case analysis on whether u = b and whether v = b reveals that any hypothetical escape of v from U' would contradict one of the four non-existence conditions.

  1. A vertex v belongs to the swapped set swap(a, b)(U) if and only if swap(a, b)(v) ∈ U.

    By definition of the image under a function, v lies in swap(a, b)(U) exactly when v = swap(a, b)(u) for some u ∈ U. Since swapping is an involution (`Equiv.swap_apply_self`), applying the swap to both sides gives swap(a, b)(v) = u ∈ U. Conversely, if swap(a, b)(v) ∈ U, applying the swap again shows that v is the image of swap(a, b)(v).

    lines 5–10

    uses Equiv.swap_apply_self

      constructor
      · intro hv
        obtain ⟨u,hu,rfl⟩ := Finset.mem_image.1 hv
        simpa only [Equiv.swap_apply_self] using hu
      · intro hv
        exact Finset.mem_image.2 ⟨Equiv.swap a b v,hv,Equiv.swap_apply_self a b v⟩
  2. The swapped cut U' does not contain a, contains b, and agrees with U on all other vertices.

    Since a ∈ U and b ∉ U, we have a ≠ b. Using the swap membership lemma, a ∈ U' is equivalent to swap(a, b)(a) = b ∈ U, which is false; thus a ∉ U'. Similarly, b ∈ U' is equivalent to swap(a, b)(b) = a ∈ U, which holds; thus b ∈ U'. Any vertex v distinct from both a and b is fixed by the transposition, so v ∈ U' if and only if v ∈ U.

    lines 22–29

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

      have hab : a ≠ b := fun he => hb (he ▸ ha)
      have ha' : a ∉ U.image (Equiv.swap a b) := by
        rw [wild_swap_mem_image, Equiv.swap_apply_left]; exact hb
      have hb' : b ∈ U.image (Equiv.swap a b) := by
        rw [wild_swap_mem_image, Equiv.swap_apply_right]; exact ha
      have hmem (v : Fin n) (hva : v ≠ a) (hvb : v ≠ b) :
          v ∈ U.image (Equiv.swap a b) ↔ v ∈ U := by
        rw [wild_swap_mem_image, Equiv.swap_apply_of_ne_of_ne hva hvb]
  3. Forward direction: if the swapped cut is closed under color i, then a has no i-neighbor in U.

    Assume U' is closed under color i. If some w ∈ U with w ≠ a had c(aw) = i, then because w ∈ U and b ∉ U, w ≠ b. Being distinct from both a and b, w belongs to U'. By edge symmetry (`w279_c_swap`), c(wa) = i. The closure of U' would then force a ∈ U', contradicting a ∉ U'.

    lines 30–36

    uses Ne.symm, w279_c_swap

      constructor
      · intro hcl
        refine ⟨?_,?_,?_,?_⟩
        · intro w hw haw hc
          have hwb : w ≠ b := fun h => hb (h ▸ hw)
          have hw' := (hmem w (Ne.symm haw) hwb).2 hw
          exact ha' (hcl w hw' a (Ne.symm haw) ((w279_c_swap c (Ne.symm haw)).trans hc))
  4. Forward direction: b has no i-neighbor outside U.

    If some w ∉ U with w ≠ b had c(bw) = i, then w ≠ a (since a ∈ U). Since b ∈ U' and U' is closed under i, w must belong to U'. But for w distinct from both a and b, membership in U' implies membership in U, contradicting w ∉ U.

    lines 37–39

    uses Ne.symm

        · intro w hw hbw hc
          have hwa : w ≠ a := fun h => hw (h ▸ ha)
          exact hw ((hmem w hwa (Ne.symm hbw)).1 (hcl b hb' w hbw hc))
  5. Forward direction: the edge ab is not colored i.

    If c(ab) = i, then c(ba) = i by edge symmetry (`w279_c_swap`). Since b ∈ U' and U' is closed under i, this would force a ∈ U', which contradicts a ∉ U'.

    lines 40–41

    uses Ne.symm, w279_c_swap

        · intro _ hc
          exact ha' (hcl b hb' a (Ne.symm hab) ((w279_c_swap c (Ne.symm hab)).trans hc))
  6. Forward direction: every i-edge crossing the original cut has U-end a or outside end b.

    Let u ∈ U and v ∉ U with c(uv) = i. By `wild_closed_cut_swap_crossing_incident`, the edge must be incident to a or b: u = a ∨ u = b ∨ v = a ∨ v = b. Because u ∈ U and b ∉ U, u ≠ b. Because v ∉ U and a ∈ U, v ≠ a. Eliminating these two impossible options via propositional logic (`tauto`) leaves u = a ∨ v = b.

    lines 42–46

    uses wild_closed_cut_swap_crossing_incident

        · intro u hu v hv huv hc
          have hi := wild_closed_cut_swap_crossing_incident c i U a b hcl u v huv hu hv hc
          have hub : u ≠ b := fun h => hb (h ▸ hu)
          have hva : v ≠ a := fun h => hv (h ▸ ha)
          tauto
  7. Backward direction: if u = b ∈ U', any incident i-edge has its other end v in U'.

    Assume all four conditions. To show U' is closed under i, let u ∈ U' and let v ≠ u be a neighbor with c(uv) = i. When u = b, v must belong to U, otherwise the edge bv would cross from b to Uᶜ, contradicting the second hypothesis. Furthermore, v cannot be a, since c(ba) = c(ab) ≠ i by the third hypothesis. Thus v is distinct from both a and b, and since v ∈ U, it follows that v ∈ U'.

    lines 47–56

    uses w279_c_swap, Ne.symm

      · rintro ⟨hA,hB,hAB,hCross⟩ u hu v huv hc
        by_cases hub : u = b
        · subst u
          have hvU : v ∈ U := by by_contra hvU; exact hB v hvU huv hc
          have hva : v ≠ a := by
            intro he
            subst v
            exact hAB hab ((w279_c_swap c hab).trans hc)
          have hvb : v ≠ b := Ne.symm huv
          exact (hmem v hva hvb).2 hvU
  8. Backward direction: if u ≠ b, any incident i-edge has its other end v in U'.

    When u ∈ U' and u ≠ b, we also have u ≠ a (since a ∉ U'), so u ∈ U. If v = b, then v ∈ U' immediately. If v ≠ b, then v ≠ a because c(ua) = c(au) ≠ i by the first hypothesis. Moreover, v must lie in U, since otherwise uv would be an old crossing i-edge with u ≠ a and v ≠ b, violating the fourth hypothesis. Since v ∈ U and v is neither a nor b, we conclude v ∈ U'.

    lines 57–68

    uses w279_c_swap, Ne.symm

        · have hua : u ≠ a := fun he => ha' (he ▸ hu)
          have huU := (hmem u hua hub).1 hu
          by_cases hvb : v = b
          · exact hvb.symm ▸ hb'
          · have hva : v ≠ a := by
              intro he
              subst v
              exact hA u huU (Ne.symm huv) ((w279_c_swap c (Ne.symm huv)).trans hc)
            have hvU : v ∈ U := by
              by_contra hvU
              exact (hCross u huU v hvU huv hc).elim hua hvb
            exact (hmem v hva hvb).2 hvU
Equiv.swap_apply_self
Applying a transposition twice to an element returns the original element (a transposition is an involution).
wild_swap_mem_image
A vertex v belongs to the swapped image swap(a, b)(U) if and only if swap(a, b)(v) belongs to U.
Equiv.swap_apply_left
A transposition of a and b maps a to b.
Equiv.swap_apply_right
A transposition of a and b maps b to a.
Equiv.swap_apply_of_ne_of_ne
A transposition of a and b fixes any element distinct from both a and b.
w279_c_swap
The color of an undirected edge is symmetric in its endpoints: c(uv) = c(vu).
Ne.symm
Inequality is symmetric: if a ≠ b then b ≠ a.
wild_closed_cut_swap_crossing_incident
If the swapped cut is closed under color i, then any i-edge crossing the original cut between U and Uᶜ must be incident to a or to b.

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 1000000lemma wild_swap_mem_image {n : ℕ} (U : Finset (Fin n)) (a b v : Fin n) :    v ∈ U.image (Equiv.swap a b) ↔ Equiv.swap a b v ∈ U := by  constructor  · intro hv    obtain ⟨u,hu,rfl⟩ := Finset.mem_image.1 hv    simpa only [Equiv.swap_apply_self] using hu  · intro hv    exact Finset.mem_image.2 ⟨Equiv.swap a b v,hv,Equiv.swap_apply_self a b v⟩theorem wild_closed_cut_swap_iff {n k : ℕ}    (c : (⊤ : SimpleGraph (Fin n)).lineGraph.Coloring (Fin k))    (i : Fin k) (U : Finset (Fin n)) (a b : Fin n)    (ha : a ∈ U) (hb : b ∉ U) :    w279_closed c i (U.image (Equiv.swap a b)) ↔      (∀ w ∈ U, ∀ h : a ≠ w, c ⟨s(a,w),wild_kn_mem h⟩ ≠ i) ∧      (∀ w ∉ U, ∀ h : b ≠ w, c ⟨s(b,w),wild_kn_mem h⟩ ≠ i) ∧      (∀ h : a ≠ b, c ⟨s(a,b),wild_kn_mem h⟩ ≠ i) ∧      (∀ u ∈ U, ∀ v ∉ U, ∀ h : u ≠ v,        c ⟨s(u,v),wild_kn_mem h⟩ = i → u = a ∨ v = b) := by  have hab : a ≠ b := fun he => hb (he ▸ ha)  have ha' : a ∉ U.image (Equiv.swap a b) := by    rw [wild_swap_mem_image, Equiv.swap_apply_left]; exact hb  have hb' : b ∈ U.image (Equiv.swap a b) := by    rw [wild_swap_mem_image, Equiv.swap_apply_right]; exact ha  have hmem (v : Fin n) (hva : v ≠ a) (hvb : v ≠ b) :      v ∈ U.image (Equiv.swap a b) ↔ v ∈ U := by    rw [wild_swap_mem_image, Equiv.swap_apply_of_ne_of_ne hva hvb]  constructor  · intro hcl    refine ⟨?_,?_,?_,?_⟩    · intro w hw haw hc      have hwb : w ≠ b := fun h => hb (h ▸ hw)      have hw' := (hmem w (Ne.symm haw) hwb).2 hw      exact ha' (hcl w hw' a (Ne.symm haw) ((w279_c_swap c (Ne.symm haw)).trans hc))    · intro w hw hbw hc      have hwa : w ≠ a := fun h => hw (h ▸ ha)      exact hw ((hmem w hwa (Ne.symm hbw)).1 (hcl b hb' w hbw hc))    · intro _ hc      exact ha' (hcl b hb' a (Ne.symm hab) ((w279_c_swap c (Ne.symm hab)).trans hc))    · intro u hu v hv huv hc      have hi := wild_closed_cut_swap_crossing_incident c i U a b hcl u v huv hu hv hc      have hub : u ≠ b := fun h => hb (h ▸ hu)      have hva : v ≠ a := fun h => hv (h ▸ ha)      tauto  · rintro ⟨hA,hB,hAB,hCross⟩ u hu v huv hc    by_cases hub : u = b    · subst u      have hvU : v ∈ U := by by_contra hvU; exact hB v hvU huv hc      have hva : v ≠ a := by        intro he        subst v        exact hAB hab ((w279_c_swap c hab).trans hc)      have hvb : v ≠ b := Ne.symm huv      exact (hmem v hva hvb).2 hvU    · have hua : u ≠ a := fun he => ha' (he ▸ hu)      have huU := (hmem u hua hub).1 hu      by_cases hvb : v = b      · exact hvb.symm ▸ hb'      · have hva : v ≠ a := by          intro he          subst v          exact hA u huU (Ne.symm huv) ((w279_c_swap c (Ne.symm huv)).trans hc)        have hvU : v ∈ U := by          by_contra hvU          exact (hCross u huU v hvU huv hc).elim hua hvb        exact (hmem v hva hvb).2 hvU
See it in the graphDiscuss this resultChallenge it