wild_color_connecting_crosses_closed_cut
For a color-connecting edge set W, every nonempty proper vertex set closed under a used color has a W edge crossing to its complement.
Statement
theorem wild_color_connecting_crosses_closed_cut {n k : ℕ}
(c : (⊤ : SimpleGraph (Fin n)).lineGraph.Coloring (Fin k))
(W : Finset (Sym2 (Fin n)))
(hW : simple_graph_is_color_connecting (⊤ : SimpleGraph (Fin n)) c ↑W)
(e : (⊤ : SimpleGraph (Fin n)).edgeSet) (U : Finset (Fin n))
(hU : U.Nonempty) (hproper : U ≠ Finset.univ) (hclosed : w279_closed c (c e) U) :
∃ (u v : Fin n) (huv : u ≠ v), u ∈ U ∧ v ∉ U ∧ s(u,v) ∈ W- Source
- Structural necessity and certificate-soundness helpers for the OP-306 campaign; arXiv:2610.22142, Sections 3.3.1 and 3.3.2. These make the optimal block-partition route an equivalence at every odd order; no new exact wild-number case or bound is asserted.
- 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…
- simple_graph_is_color_connectingLet γ be an edge colouring of a graph G. A set W of edges of G is colour-connecting if, for every colour c used by γ, the spanning…
- Used by 2
- wild_block_cut_of_color_connectingA rooted vertex partition whose blocks contain both endpoints of every wild edge has an edge of every used color across every nonempty…
- wild_odd_color_connecting_closed_block_card_ge_threeIn a proper complete-graph edge coloring at odd order n>=3, every nonempty vertex block with no wild edge crossing its boundary has at…
The proof, explained
The proof argues by contradiction: if no edge of W crosses from U to its complement, then U is closed under adjacency in the graph H formed by the edges of color c(e) together with W. Because W is color-connecting, H is connected, so every vertex is reachable from U by a walk and therefore must also belong to U. This makes U the entire vertex set, contradicting the assumption that U is a proper subset.
It suffices to derive a contradiction from the assumption that no edge in W crosses from U to its complement.
We proceed by contradiction (`by_contra! hn`), assuming that for every pair of distinct vertices u and v, if u ∈ U and v ∉ U, then the edge s(u, v) is not in W.
classical by_contra! hn
The graph H formed by the edges of color c(e) together with the edges of W is connected.
We define H as the simple graph whose edges are those of color c(e) in the complete graph plus the edges in W. By the second condition in the definition of a color-connecting set (`hW.2 e`), this graph H is connected.
let H := SimpleGraph.fromEdgeSet ({f | ∃ hf : f ∈ (⊤ : SimpleGraph (Fin n)).edgeSet, c ⟨f,hf⟩ = c e} ∪ (↑W : Set (Sym2 (Fin n)))) have hH : H.Connected := hW.2 e
The vertex set U is closed under adjacency in H: if u ∈ U and v is adjacent to u in H, then v ∈ U.
Let u ∈ U and let v be a neighbor of u in H. By definition of adjacency in an edge-induced subgraph (`SimpleGraph.fromEdgeSet_adj`), the edge s(u, v) is in H and u ≠ v. Thus s(u, v) either has color c(e) or belongs to W. If it has color c(e), then v ∈ U because U is closed under color c(e) (`hclosed`). If s(u, v) ∈ W, then v cannot be outside U, since that would contradict the assumption (`hn`) that no edge of W crosses between U and its complement. Hence v ∈ U in either case.
uses
SimpleGraph.fromEdgeSet_adj,Finset.mem_coe.1have hstay : ∀ u ∈ U, ∀ v, H.Adj u v → v ∈ U := by intro u hu v hv rw [SimpleGraph.fromEdgeSet_adj] at hv rcases hv with ⟨⟨he,hc⟩ | hw,hne⟩ · exact hclosed u hu v hne hc · by_contra hnv exact hn u v hne hu hnv (Finset.mem_coe.1 hw)
Every vertex in the graph belongs to U.
Since U is nonempty, we pick a vertex u ∈ U. For any vertex v, the connectedness of H yields a walk p from u to v. By induction on the length of walks in H, any walk starting in U remains in U at every step, because each step stays within U by the previous step's closure property (`hstay`). Therefore, the destination v must belong to U.
obtain ⟨u,hu⟩ := hU have hall : ∀ v : Fin n, v ∈ U := by intro v obtain ⟨p⟩ := hH.preconnected u v have walkstay : ∀ {x y : Fin n}, H.Walk x y → x ∈ U → y ∈ U := by intro x y p induction p with | nil => exact id | cons hx p ih => exact fun hxU => ih (hstay _ hxU _ hx) exact walkstay p hu
Contradiction: U cannot be both a proper subset and the entire vertex set.
Because every vertex of Fin n belongs to U, U is the universal finset by `Finset.eq_univ_of_forall`. This contradicts the hypothesis `hproper` that U ≠ Finset.univ.
uses
Finset.eq_univ_of_forallexact hproper (Finset.eq_univ_of_forall hall)
SimpleGraph.fromEdgeSet_adj- Two distinct vertices v and w are adjacent in the graph constructed from an edge set s if and only if the undirected pair s(v, w) belongs to s.
Finset.mem_coe.1- Membership of an element in the coercion of a finset to a set implies membership in the finset itself.
Finset.eq_univ_of_forall- A finset of a finite type equals the universal finset (the whole type) if every element of the type belongs to it.
- In Lean, the fact that a connected graph has all vertices in the same connected component as a given vertex is proved by induction on the path (`SimpleGraph.Walk`), which on paper is usually stated directly as connectedness.
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 BigOperators Classicalset_option maxHeartbeats 1600000set_option maxRecDepth 100000theorem wild_color_connecting_crosses_closed_cut {n k : ℕ} (c : (⊤ : SimpleGraph (Fin n)).lineGraph.Coloring (Fin k)) (W : Finset (Sym2 (Fin n))) (hW : simple_graph_is_color_connecting (⊤ : SimpleGraph (Fin n)) c ↑W) (e : (⊤ : SimpleGraph (Fin n)).edgeSet) (U : Finset (Fin n)) (hU : U.Nonempty) (hproper : U ≠ Finset.univ) (hclosed : w279_closed c (c e) U) : ∃ (u v : Fin n) (huv : u ≠ v), u ∈ U ∧ v ∉ U ∧ s(u,v) ∈ W := by classical by_contra! hn let H := SimpleGraph.fromEdgeSet ({f | ∃ hf : f ∈ (⊤ : SimpleGraph (Fin n)).edgeSet, c ⟨f,hf⟩ = c e} ∪ (↑W : Set (Sym2 (Fin n)))) have hH : H.Connected := hW.2 e have hstay : ∀ u ∈ U, ∀ v, H.Adj u v → v ∈ U := by intro u hu v hv rw [SimpleGraph.fromEdgeSet_adj] at hv rcases hv with ⟨⟨he,hc⟩ | hw,hne⟩ · exact hclosed u hu v hne hc · by_contra hnv exact hn u v hne hu hnv (Finset.mem_coe.1 hw) obtain ⟨u,hu⟩ := hU have hall : ∀ v : Fin n, v ∈ U := by intro v obtain ⟨p⟩ := hH.preconnected u v have walkstay : ∀ {x y : Fin n}, H.Walk x y → x ∈ U → y ∈ U := by intro x y p induction p with | nil => exact id | cons hx p ih => exact fun hxU => ih (hstay _ hxU _ hx) exact walkstay p hu exact hproper (Finset.eq_univ_of_forall hall)