AFTD Auto-Formalizing Theoretical Domains

wild_color_connecting_crosses_closed_cut

theoremverified

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

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.

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

    lines 12–13

      classical
      by_contra! hn
  2. 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.

    lines 14–15

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

    lines 16–22

    uses SimpleGraph.fromEdgeSet_adj, Finset.mem_coe.1

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

    lines 23–32

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

    line 33

    uses Finset.eq_univ_of_forall

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

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