wild_closed_cut_swap_color_invariant
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
- 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…
- 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⌋.
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.
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.
uses
Ne.symm,w279_c_swaphave 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)⟩
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.
uses
wild_swap_mem_image,Equiv.swap_apply_left,Equiv.swap_apply_right,Equiv.swap_apply_of_ne_of_neext 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]
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.
uses
wild_swap_mem_image,Equiv.swap_apply_selfconstructor · 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
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.
· 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
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_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