wild_closed_cut_swap_crossing_incident
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
- 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 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.
Assume for contradiction that neither u nor v is a or b.
Assume the negation of the conclusion.
by_contra! h
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.
uses
Equiv.swap_apply_of_ne_of_ne,Finset.mem_image.2have 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⟩
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.
have hv' := hclosed u hu' v huv hcThe 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.
uses
Finset.mem_image.1obtain ⟨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
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 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)