wild_closed_cut_swap_crossing_card_le_two
For 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 ordered color-i edges cross the original cut from U to its complement.
Statement
theorem wild_closed_cut_swap_crossing_card_le_two {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))) : ((Finset.univ : Finset (Fin n × Fin n)).filter (fun uv => ∃ h : uv.1 ≠ uv.2, uv.1 ∈ U ∧ uv.2 ∉ U ∧ c ⟨s(uv.1,uv.2),wild_kn_mem h⟩ = i)).card ≤ 2
- 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⌋.
The proof, explained
To bound the number of ordered color-i edges crossing from U to its complement by 2, we define a function f to {0, 1} that maps an edge to 0 if it contains the vertex a, and to 1 otherwise. Because the cut swapped by (a b) is closed under color-i edges, every crossing color-i edge is incident to a or b; hence two crossing edges with the same f-value must share an endpoint (both contain a or both contain b). In a properly edge-colored complete graph, two crossing edges cannot share an endpoint at opposite sides of the cut (as that endpoint would be both in and out of U) nor at the same side (which would violate proper coloring at that vertex), so sharing an endpoint forces equality. Thus f is injective, and since its codomain has size 2, there are at most two such crossing edges.
Define the set E of ordered color-i edges crossing from U to its complement, and define a function f : E → {0, 1} indicating incidence to a.
We let E be the finset of ordered pairs (u, v) such that u ≠ v, u ∈ U, v ∉ U, and the edge {u, v} has color i. We then define f : Fin n × Fin n → Fin 2 by mapping (u, v) to 0 if either u = a or v = a, and to 1 otherwise.
uses
wild_kn_memclassical let E := ((Finset.univ : Finset (Fin n × Fin n)).filter (fun uv => ∃ h : uv.1 ≠ uv.2, uv.1 ∈ U ∧ uv.2 ∉ U ∧ c ⟨s(uv.1,uv.2),wild_kn_mem h⟩ = i)) let f : Fin n × Fin n → Fin 2 := fun uv => if uv.1 = a ∨ uv.2 = a then 0 else 1
To prove f is injective on E, take x, y ∈ E with f(x) = f(y); each edge x and y must be incident to a or b.
We unpack the assumption that x, y ∈ E satisfy f(x) = f(y). By definition of E, both x and y are ordered pairs of distinct vertices crossing from U to its complement with color i. Applying wild_closed_cut_swap_crossing_incident with the hypothesis that the swapped cut is color-i closed, every such crossing edge must have at least one endpoint in {a, b}.
uses
wild_closed_cut_swap_crossing_incidenthave hf : Set.InjOn f (↑E) := by intro x hx y hy hxy obtain ⟨hxne,hxU,hxnU,hxc⟩ := (Finset.mem_filter.1 hx).2 obtain ⟨hyne,hyU,hynU,hyc⟩ := (Finset.mem_filter.1 hy).2 have hxinc := wild_closed_cut_swap_crossing_incident c i U a b hclosed x.1 x.2 hxne hxU hxnU hxc have hyinc := wild_closed_cut_swap_crossing_incident c i U a b hclosed y.1 y.2 hyne hyU hynU hyc
The edges x and y either both contain a or both contain b.
Unfolding the definition of f, if f(x) = f(y) = 0, then both x and y are incident to a (using Or.inl). The mixed cases 0 = 1 and 1 = 0 are ruled out by numerical disequality. If f(x) = f(y) = 1, then neither x nor y is incident to a; since each must be incident to a or b, propositional logic shows that both must be incident to b (using Or.inr).
uses
Or.inl,Or.inrhave common : (x.1 = a ∨ x.2 = a) ∧ (y.1 = a ∨ y.2 = a) ∨ (x.1 = b ∨ x.2 = b) ∧ (y.1 = b ∨ y.2 = b) := by simp only [f] at hxy split_ifs at hxy with hxa hya · exact Or.inl ⟨hxa,hya⟩ · norm_num at hxy · norm_num at hxy · exact Or.inr ⟨by tauto, by tauto⟩
If two crossing edges x, y ∈ E share any endpoint z, then x = y.
We analyze which component of x and y equals z. If both have first component z (x.1 = y.1 = z), wild_kn_same_color implies x.2 = y.2 since a vertex cannot have two incident edges of color i, so x = y by Prod.ext. If x.1 = z and y.2 = z, then z ∈ U and z ∉ U, which is contradictory and dismissed by False.elim; the symmetric case x.2 = z and y.1 = z is similarly impossible. If both have second component z (x.2 = y.2 = z), by symmetry of edge colors (w279_c_swap) and Ne.symm, wild_kn_same_color again yields x.1 = y.1, so x = y by Prod.ext.
uses
wild_kn_same_color,Prod.ext,False.elim,Ne.symm,w279_c_swaphave hshare : ∀ z, (x.1 = z ∨ x.2 = z) → (y.1 = z ∨ y.2 = z) → x = y := by intro z hxz hyz rcases hxz with hxz | hxz <;> rcases hyz with hyz | hyz · have hfst : x.1 = y.1 := hxz.trans hyz.symm have hsnd : x.2 = y.2 := wild_kn_same_color c hxne (by simpa only [← hfst] using hyne) (by simpa only [← hfst] using hxc.trans hyc.symm) exact Prod.ext hfst hsnd · exact False.elim (hynU (hyz.symm ▸ hxz ▸ hxU)) · exact False.elim (hxnU (hxz.symm ▸ hyz ▸ hyU)) · have hsnd : x.2 = y.2 := hxz.trans hyz.symm have hfst : x.1 = y.1 := wild_kn_same_color c (Ne.symm hxne) (by simpa only [← hsnd] using Ne.symm hyne) (by have hxcol := (w279_c_swap c (Ne.symm hxne)).trans hxc have hycol := (w279_c_swap c (Ne.symm hyne)).trans hyc simpa only [← hsnd] using hxcol.trans hycol.symm) exact Prod.ext hfst hsnd
The map f is injective on E.
From the fact that x and y either both contain a or both contain b, we instantiate the sharing lemma with z = a or z = b respectively, showing that x = y in either case.
rcases common with ⟨hx,hy⟩ | ⟨hx,hy⟩ · exact hshare a hx hy · exact hshare b hx hy
The number of crossing color-i edges is at most 2.
Since f : E → Fin 2 is injective on E and maps into Finset.univ (by Finset.mem_univ), Finset.card_le_card_of_injOn bounds the cardinality of E by the size of Finset.univ. Applying Finset.card_univ and Fintype.card_fin, the size of Fin 2 is 2, which completes the proof.
uses
Finset.card_le_card_of_injOn,Finset.mem_univ,Finset.card_univ,Fintype.card_finhave hc := Finset.card_le_card_of_injOn f (fun _ _ => Finset.mem_univ _) hf simpa only [Finset.card_univ,Fintype.card_fin] using hc
wild_kn_mem- In a complete graph, any pair of distinct vertices forms an edge.
wild_closed_cut_swap_crossing_incident- If the cut obtained by swapping vertices a and b is closed under color-i edges, then every edge crossing the original cut with color i has at least one endpoint in {a, b}.
Or.inl- The left introduction rule for disjunction: if P holds, then P ∨ Q holds.
Or.inr- The right introduction rule for disjunction: if Q holds, then P ∨ Q holds.
wild_kn_same_color- In a properly edge-colored complete graph, if two edges incident to a vertex u have the same color, their other endpoints must be equal.
Prod.ext- Two ordered pairs are equal if and only if their first components are equal and their second components are equal.
False.elim- From a contradiction (False), any proposition follows (principle of explosion).
Ne.symm- Inequality is symmetric: if u ≠ v, then v ≠ u.
w279_c_swap- The color of an edge is invariant under swapping the order of its endpoints.
Finset.card_le_card_of_injOn- If a function between finite sets is injective on a subset, the cardinality of the domain subset is at most that of the codomain.
Finset.mem_univ- Every element of a finite type belongs to its universal finset.
Finset.card_univ- The cardinality of the universal finset of a finite type equals the cardinality of the type.
Fintype.card_fin- The standard finite type Fin n has cardinality n.
- Proper edge colorings of the complete graph on n vertices are formalized as vertex colorings of its line graph ⊤.lineGraph.
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_card_le_two {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))) : ((Finset.univ : Finset (Fin n × Fin n)).filter (fun uv => ∃ h : uv.1 ≠ uv.2, uv.1 ∈ U ∧ uv.2 ∉ U ∧ c ⟨s(uv.1,uv.2),wild_kn_mem h⟩ = i)).card ≤ 2 := by classical let E := ((Finset.univ : Finset (Fin n × Fin n)).filter (fun uv => ∃ h : uv.1 ≠ uv.2, uv.1 ∈ U ∧ uv.2 ∉ U ∧ c ⟨s(uv.1,uv.2),wild_kn_mem h⟩ = i)) let f : Fin n × Fin n → Fin 2 := fun uv => if uv.1 = a ∨ uv.2 = a then 0 else 1 have hf : Set.InjOn f (↑E) := by intro x hx y hy hxy obtain ⟨hxne,hxU,hxnU,hxc⟩ := (Finset.mem_filter.1 hx).2 obtain ⟨hyne,hyU,hynU,hyc⟩ := (Finset.mem_filter.1 hy).2 have hxinc := wild_closed_cut_swap_crossing_incident c i U a b hclosed x.1 x.2 hxne hxU hxnU hxc have hyinc := wild_closed_cut_swap_crossing_incident c i U a b hclosed y.1 y.2 hyne hyU hynU hyc have common : (x.1 = a ∨ x.2 = a) ∧ (y.1 = a ∨ y.2 = a) ∨ (x.1 = b ∨ x.2 = b) ∧ (y.1 = b ∨ y.2 = b) := by simp only [f] at hxy split_ifs at hxy with hxa hya · exact Or.inl ⟨hxa,hya⟩ · norm_num at hxy · norm_num at hxy · exact Or.inr ⟨by tauto, by tauto⟩ have hshare : ∀ z, (x.1 = z ∨ x.2 = z) → (y.1 = z ∨ y.2 = z) → x = y := by intro z hxz hyz rcases hxz with hxz | hxz <;> rcases hyz with hyz | hyz · have hfst : x.1 = y.1 := hxz.trans hyz.symm have hsnd : x.2 = y.2 := wild_kn_same_color c hxne (by simpa only [← hfst] using hyne) (by simpa only [← hfst] using hxc.trans hyc.symm) exact Prod.ext hfst hsnd · exact False.elim (hynU (hyz.symm ▸ hxz ▸ hxU)) · exact False.elim (hxnU (hxz.symm ▸ hyz ▸ hyU)) · have hsnd : x.2 = y.2 := hxz.trans hyz.symm have hfst : x.1 = y.1 := wild_kn_same_color c (Ne.symm hxne) (by simpa only [← hsnd] using Ne.symm hyne) (by have hxcol := (w279_c_swap c (Ne.symm hxne)).trans hxc have hycol := (w279_c_swap c (Ne.symm hyne)).trans hyc simpa only [← hsnd] using hxcol.trans hycol.symm) exact Prod.ext hfst hsnd rcases common with ⟨hx,hy⟩ | ⟨hx,hy⟩ · exact hshare a hx hy · exact hshare b hx hy have hc := Finset.card_le_card_of_injOn f (fun _ _ => Finset.mem_univ _) hf simpa only [Finset.card_univ,Fintype.card_fin] using hc