AFTD Auto-Formalizing Theoretical Domains

wild_block_cut_of_color_connecting

theoremverified

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
Used by 1

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.

  1. 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\}$.

    lines 14–17

      classical
      intro e S hS hproper
      by_contra! hno
      let U : Finset (Fin n) := Finset.univ.filter fun v => p v ∈ S
  2. $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$.

    lines 18–21

    uses Finset.mem_univ

      have hU : U.Nonempty := by
        obtain ⟨t,ht⟩ := hS
        refine ⟨r t,Finset.mem_filter.2 ⟨Finset.mem_univ _,?_⟩⟩
        rwa [hr]
  3. $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.

    lines 22–28

    uses Finset.eq_univ_of_forall, Finset.mem_univ, Finset.mem_filter, true_and

      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
  4. $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$.

    lines 29–34

    uses Finset.mem_univ

      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
  5. 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$.

    line 35

    uses wild_color_connecting_crosses_closed_cut

      obtain ⟨u,v,huv,hu,hv,hw⟩ := wild_color_connecting_crosses_closed_cut c W hW e U hU hUproper hclosed
  6. Contradiction: 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$.

    lines 36–38

    uses Finset.mem_univ

      have 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.

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

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⟩
See it in the graphDiscuss this resultChallenge it