wild_block_cut_of_color_connecting
A rooted vertex partition whose blocks contain both endpoints of every wild edge has an edge of every used color across every nonempty proper block cut whenever the wild edge set is color-connecting.
Statement
theorem wild_block_cut_of_color_connecting {n k q : ℕ}
(c : (⊤ : SimpleGraph (Fin n)).lineGraph.Coloring (Fin k))
(W : Finset (Sym2 (Fin n)))
(hW : simple_graph_is_color_connecting (⊤ : SimpleGraph (Fin n)) c ↑W)
(p : Fin n → Fin q) (r : Fin q → Fin n) (hr : ∀ t, p (r t) = t)
(hstay : ∀ (u v : Fin n) (huv : u ≠ v), s(u,v) ∈ W → p u = p v) :
∀ (e : (⊤ : SimpleGraph (Fin n)).edgeSet) (S : Finset (Fin q)),
S.Nonempty → S ≠ Finset.univ →
∃ (u v : Fin n) (huv : u ≠ v), p u ∈ S ∧ p v ∉ S ∧ c ⟨s(u,v),wild_kn_mem huv⟩ = c e- 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 4
- wild_color_connecting_crosses_closed_cutFor a color-connecting edge set W, every nonempty proper vertex set closed under a used color has a W edge crossing to its complement.
- 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…
- 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_odd_optimal_color_connecting_partitionAt odd order n>=3, every color-connecting edge set of size n-floor(n/3) in a proper complete-graph edge coloring yields a rooted partition…
The proof, explained
The theorem is proved by contradiction: suppose there is no edge of color $c(e)$ crossing between a nonempty proper set of blocks $S$ and its complement. Defining $U = p^{-1}(S)$ yields a nonempty proper vertex cut that is closed under edges of color $c(e)$ by the contradiction hypothesis. Since $W$ is color-connecting, the lemma `wild_color_connecting_crosses_closed_cut` produces a wild edge in $W$ crossing the cut $U$. But the hypothesis that wild edges stay within blocks implies both endpoints of this edge must lie in $U$, contradicting the fact that the edge crosses the cut.
Assume for contradiction that no edge of color $c(e)$ crosses the block cut $S$, and define $U$ as the preimage of $S$ under $p$.
We introduce the target edge $e$, the nonempty proper subset $S \subsetneq \mathrm{Fin}\;q$ of block labels, and assume for contradiction that no edge $\{u, v\}$ with $p(u) \in S$ and $p(v) \notin S$ has color $c(e)$. We then define $U \subseteq \mathrm{Fin}\;n$ to be the preimage $p^{-1}(S) = \{v \mid p(v) \in S\}$.
classical intro e S hS hproper by_contra! hno let U : Finset (Fin n) := Finset.univ.filter fun v => p v ∈ S
$U$ is nonempty.
Since $S$ is nonempty, it contains some block label $t$. Using the section $r$, the vertex $r(t)$ satisfies $p(r(t)) = t \in S$, which places $r(t) \in U$.
uses
Finset.mem_univhave hU : U.Nonempty := by obtain ⟨t,ht⟩ := hS refine ⟨r t,Finset.mem_filter.2 ⟨Finset.mem_univ _,?_⟩⟩ rwa [hr]
$U$ is a proper subset of vertices ($U \ne \mathrm{Finset.univ}$).
If $U$ were the entire vertex set $\mathrm{Finset.univ}$, then every root $r(t)$ for $t \in \mathrm{Fin}\;q$ would belong to $U$. By definition of $U$, this would mean $p(r(t)) = t \in S$ for every $t$, which implies $S = \mathrm{Finset.univ}$, contradicting the hypothesis that $S$ is a proper subset.
uses
Finset.eq_univ_of_forall,Finset.mem_univ,Finset.mem_filter,true_andhave hUproper : U ≠ Finset.univ := by intro hh apply hproper apply Finset.eq_univ_of_forall intro t have ht : r t ∈ U := hh ▸ Finset.mem_univ _ simpa only [U,Finset.mem_filter,Finset.mem_univ,true_and,hr] using ht
$U$ is closed under edges of color $c(e)$ (`w279_closed c (c e) U`).
Suppose $u \in U$ and $\{u, v\}$ is an edge of color $c(e)$. If $v \notin U$, then $p(u) \in S$ and $p(v) \notin S$, meaning $\{u, v\}$ crosses the cut with color $c(e)$, which directly contradicts the nonexistence assumption `hno`. Hence $v \in U$.
uses
Finset.mem_univhave hclosed : w279_closed c (c e) U := by intro u hu v huv hc apply Finset.mem_filter.2 refine ⟨Finset.mem_univ _,?_⟩ by_contra hv exact hno u v huv (Finset.mem_filter.1 hu).2 hv hc
There exists a wild edge in $W$ crossing between $U$ and its complement.
Because $W$ is color-connecting and $U$ is a nonempty proper cut closed under edges of color $c(e)$, the theorem `wild_color_connecting_crosses_closed_cut` guarantees the existence of vertices $u \in U$ and $v \notin U$ such that $\{u, v\} \in W$.
uses
wild_color_connecting_crosses_closed_cutobtain ⟨u,v,huv,hu,hv,hw⟩ := wild_color_connecting_crosses_closed_cut c W hW e U hU hUproper hclosedContradiction: the outside vertex $v$ must belong to $U$.
Since $u \in U$, we have $p(u) \in S$. The hypothesis `hstay` ensures that any wild edge $\{u, v\} \in W$ has both endpoints in the same block, so $p(v) = p(u) \in S$. This places $v \in U$, contradicting the fact that $v \notin U$.
uses
Finset.mem_univhave huS := (Finset.mem_filter.1 hu).2 apply hv exact Finset.mem_filter.2 ⟨Finset.mem_univ _,(hstay u v huv hw) ▸ huS⟩
Finset.mem_univ- Every element of a finite type belongs to `Finset.univ`.
Finset.eq_univ_of_forall- A finite set containing every element of its ambient type is equal to `Finset.univ`.
Finset.mem_filter- An element belongs to `Finset.filter p s` if and only if it belongs to `s` and satisfies `p`.
true_and- The proposition `True ∧ p` is logically equivalent to `p`.
wild_color_connecting_crosses_closed_cut- If a set of wild edges is color-connecting, then across every nonempty proper cut closed under edges of color $c(e)$, there is at least one wild edge.
- The predicate `w279_closed c (c e) U` is an auxiliary definition in this formal development stating that no edge of color $c(e)$ crosses between $U$ and its complement; that is, any edge of color $c(e)$ with one endpoint in $U$ must have its other endpoint in $U$ as well.
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_block_cut_of_color_connecting {n k q : ℕ} (c : (⊤ : SimpleGraph (Fin n)).lineGraph.Coloring (Fin k)) (W : Finset (Sym2 (Fin n))) (hW : simple_graph_is_color_connecting (⊤ : SimpleGraph (Fin n)) c ↑W) (p : Fin n → Fin q) (r : Fin q → Fin n) (hr : ∀ t, p (r t) = t) (hstay : ∀ (u v : Fin n) (huv : u ≠ v), s(u,v) ∈ W → p u = p v) : ∀ (e : (⊤ : SimpleGraph (Fin n)).edgeSet) (S : Finset (Fin q)), S.Nonempty → S ≠ Finset.univ → ∃ (u v : Fin n) (huv : u ≠ v), p u ∈ S ∧ p v ∉ S ∧ c ⟨s(u,v),wild_kn_mem huv⟩ = c e := by classical intro e S hS hproper by_contra! hno let U : Finset (Fin n) := Finset.univ.filter fun v => p v ∈ S have hU : U.Nonempty := by obtain ⟨t,ht⟩ := hS refine ⟨r t,Finset.mem_filter.2 ⟨Finset.mem_univ _,?_⟩⟩ rwa [hr] have hUproper : U ≠ Finset.univ := by intro hh apply hproper apply Finset.eq_univ_of_forall intro t have ht : r t ∈ U := hh ▸ Finset.mem_univ _ simpa only [U,Finset.mem_filter,Finset.mem_univ,true_and,hr] using ht have hclosed : w279_closed c (c e) U := by intro u hu v huv hc apply Finset.mem_filter.2 refine ⟨Finset.mem_univ _,?_⟩ by_contra hv exact hno u v huv (Finset.mem_filter.1 hu).2 hv hc obtain ⟨u,v,huv,hu,hv,hw⟩ := wild_color_connecting_crosses_closed_cut c W hW e U hU hUproper hclosed have huS := (Finset.mem_filter.1 hu).2 apply hv exact Finset.mem_filter.2 ⟨Finset.mem_univ _,(hstay u v huv hw) ▸ huS⟩