wild_closed_cut_swap_iff
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
- wild_closed_cut_swap_crossing_incidentFor 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…
- wild_number_complete_graph_279_min_proper_coloring_eqNew case of OP-306: every minimum proper edge colouring of K_279 has wild number 186 = floor(4*ceil(279/2)/3). The lower bound is the…
- wild_number_complete_graph_min_proper_coloring_geLet n ≥ 3 and let ρ be a minimum proper edge colouring of K_n (a proper colouring with χ'(K_n) colours). Then wld_ρ(K_n) ≥ ⌊4⌈n/2⌉/3⌋.
- Used by 1
- wild_closed_cut_swap_color_invariantSwapping the endpoints of a color-i edge in a proper complete-graph edge coloring preserves whether each vertex cut is closed for color i.
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.
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).
uses
Equiv.swap_apply_selfconstructor · 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⟩
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.
uses
wild_swap_mem_image,Equiv.swap_apply_left,Equiv.swap_apply_right,Equiv.swap_apply_of_ne_of_nehave 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]
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'.
uses
Ne.symm,w279_c_swapconstructor · 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))
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.
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))
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'.
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))
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.
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
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'.
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 hvUBackward 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'.
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.
- The deduction that an old crossing i-edge must have its U-endpoint a or outside endpoint b uses the automated propositional tactic `tauto` to rule out the impossible cases u = b and v = a from the four-way disjunction provided by `wild_closed_cut_swap_crossing_incident`.
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.
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