AFTD Auto-Formalizing Theoretical Domains

wild_odd_optimal_color_connecting_partition

theoremverified

At 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 into floor(n/3) blocks, each of size at least three, with every used color crossing every nontrivial block cut.

Statement

theorem wild_odd_optimal_color_connecting_partition {n k : ℕ} (hn : 3 ≤ n) (hodd : n%2=1)
    (c : (⊤ : SimpleGraph (Fin n)).lineGraph.Coloring (Fin k))
    (W : Finset (Sym2 (Fin n)))
    (hW : simple_graph_is_color_connecting (⊤ : SimpleGraph (Fin n)) c ↑W)
    (hcard : W.card = n-n/3) :
    ∃ (p : Fin n → Fin (n/3)) (r : Fin (n/3) → Fin n),
      (∀ t, p (r t) = t) ∧
      (∀ t, 3 ≤ ((Finset.univ : Finset (Fin n)).filter fun v => p v = t).card) ∧
      (∀ (e : (⊤ : SimpleGraph (Fin n)).edgeSet) (S : Finset (Fin (n/3))),
        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 5
Used by 1

The proof, explained

Consider the subgraph G spanned by the color-connecting edge set W. In an odd-order complete graph, every connected component of G is closed under edges of W and must contain at least 3 vertices, forcing the number of components to satisfy 3 c(G) ≤ n, or c(G) ≤ ⌊n/3⌋. On the other hand, the general graph bound n ≤ |E(G)| + c(G) with |E(G)| ≤ |W| = n - ⌊n/3⌋ implies c(G) ≥ ⌊n/3⌋, so G has exactly ⌊n/3⌋ components. Identifying the components with Fin (n/3) yields a rooted partition into blocks of size at least 3, and because edges in W never cross between components, the block-cut theorem guarantees that every color crosses every nontrivial block cut.

  1. Let G be the graph on Fin n induced by the edge set W.

    We enable classical reasoning and define G as the simple graph on vertex set Fin n whose edge set is determined by W.

    lines 16–17

    uses SimpleGraph.fromEdgeSet

      classical
      let G : SimpleGraph (Fin n) := SimpleGraph.fromEdgeSet (↑W : Set (Sym2 (Fin n)))
  2. Every connected component of G has at least 3 vertices.

    For any connected component C of G, its vertex set is nonempty (it contains its canonical representative `C.out`) and has no crossing edges in W: if u ∈ C, v ∉ C, and {u, v} ∈ W, then u and v are adjacent in G, which would force v ∈ C. By `wild_odd_color_connecting_closed_block_card_ge_three`, any nonempty vertex set closed under edges of W in an odd complete graph must contain at least 3 vertices.

    lines 18–25

    uses wild_odd_color_connecting_closed_block_card_ge_three, SimpleGraph.fromEdgeSet_adj

      have hmin : ∀ C : G.ConnectedComponent, 3 ≤ C.supp.toFinset.card := by
        intro C
        apply wild_odd_color_connecting_closed_block_card_ge_three hn hodd c W hW C.supp.toFinset
        · exact ⟨C.out,Set.mem_toFinset.2 C.out_eq⟩
        · intro u v huv hu hv hw
          have hadj : G.Adj u v := (SimpleGraph.fromEdgeSet_adj (↑W : Set (Sym2 (Fin n)))).2 ⟨Finset.mem_coe.2 hw,huv⟩
          apply hv
          exact Set.mem_toFinset.2 ((C.mem_supp_congr_adj hadj).1 (Set.mem_toFinset.1 hu))
  3. The sum of component sizes is n, which implies 3 * |G.ConnectedComponent| ≤ n.

    Because the connected components partition the n vertices of G, summing their sizes fiberwise yields n. Since every component has size at least 3, summing this bound over all components yields 3 * |G.ConnectedComponent| ≤ n.

    lines 26–39

    uses Finset.card_eq_sum_card_fiberwise, Finset.sum_le_sum

      have hsumV : (∑ C : G.ConnectedComponent, C.supp.toFinset.card) = n := by
        have hi := Finset.card_eq_sum_card_fiberwise (f := G.connectedComponentMk)
          (s := (Finset.univ : Finset (Fin n))) (t := (Finset.univ : Finset G.ConnectedComponent))
          (fun _ _ => Finset.mem_univ _)
        have hA : ∀ C : G.ConnectedComponent, C.supp.toFinset = Finset.univ.filter (fun v => G.connectedComponentMk v = C) := by
          intro C
          ext v
          simp only [Set.mem_toFinset,SimpleGraph.ConnectedComponent.mem_supp_iff,Finset.mem_filter,Finset.mem_univ,true_and]
        simp_rw [hA]
        simpa only [Finset.card_univ,Fintype.card_fin] using hi.symm
      have hcmin : 3 * Fintype.card G.ConnectedComponent ≤ n := by
        have hi := Finset.sum_le_sum (fun C (_ : C ∈ (Finset.univ : Finset G.ConnectedComponent)) => hmin C)
        simp only [hsumV,Finset.sum_const,Finset.card_univ,nsmul_eq_mul,mul_comm] at hi
        exact_mod_cast hi
  4. The number of edges in G is at most |W|, and n ≤ |E(G)| + |G.ConnectedComponent|.

    By definition the edges of G form a subset of W, so |E(G)| ≤ |W| = n - ⌊n/3⌋. The general graph inequality `simple_graph_card_vertices_le_edges_add_components` bounds the number of vertices by the number of edges plus the number of components. Converting the counts to `Nat.card` prepares them for linear arithmetic.

    lines 40–51

    uses Finset.card_le_card, simple_graph_card_vertices_le_edges_add_components, Nat.card_eq_fintype_card

      have hEdges : G.edgeFinset.card ≤ W.card := by
        apply Finset.card_le_card
        intro e he
        have he' : e ∈ G.edgeSet := SimpleGraph.mem_edgeFinset.1 he
        exact (SimpleGraph.edgeSet_fromEdgeSet (↑W : Set (Sym2 (Fin n))) ▸ he').1
      have hcmax : n ≤ Nat.card G.edgeSet + Nat.card G.ConnectedComponent := by
        have hi := simple_graph_card_vertices_le_edges_add_components G
        simpa only [SimpleGraph.edgeFinset_card, ← Nat.card_eq_fintype_card,Nat.card_fin] using hi
      have hcmin' : 3 * Nat.card G.ConnectedComponent ≤ n := by
        simpa only [← Nat.card_eq_fintype_card] using hcmin
      have hEdges' : Nat.card G.edgeSet ≤ W.card := by
        simpa only [SimpleGraph.edgeFinset_card, ← Nat.card_eq_fintype_card] using hEdges
  5. The graph G has exactly ⌊n/3⌋ connected components. automation

    From 3 c(G) ≤ n we obtain c(G) ≤ ⌊n/3⌋, while n ≤ |E(G)| + c(G) ≤ n - ⌊n/3⌋ + c(G) yields c(G) ≥ ⌊n/3⌋. The integer arithmetic tactic `omega` closes the equality c(G) = ⌊n/3⌋, for both `Nat.card` and `Fintype.card`.

    lines 52–53

    uses Nat.card_eq_fintype_card

      have hcc' : Nat.card G.ConnectedComponent = n/3 := by omega
      have hcc : Fintype.card G.ConnectedComponent = n/3 := by simpa only [Nat.card_eq_fintype_card] using hcc' 
  6. Define the partition map p : Fin n → Fin (n/3) and root section r : Fin (n/3) → Fin n satisfying p (r t) = t.

    Since G has exactly ⌊n/3⌋ connected components, we choose a bijection E between components and Fin (n/3). The partition map p assigns each vertex v to E([v]), and r(t) picks the canonical representative of component E⁻¹(t). The identity p (r t) = t follows directly by applying E to the fact that the representative belongs to E⁻¹(t).

    lines 54–60

    uses Fintype.equivFinOfCardEq, congrArg

      let E : G.ConnectedComponent ≃ Fin (n/3) := Fintype.equivFinOfCardEq hcc
      let p : Fin n → Fin (n/3) := fun v => E (G.connectedComponentMk v)
      let r : Fin (n/3) → Fin n := fun t => (E.symm t).out
      have hr : ∀ t, p (r t) = t := by
        intro t
        change E (G.connectedComponentMk ((E.symm t).out)) = t
        exact (congrArg E (E.symm t).out_eq).trans (E.apply_symm_apply t)
  7. Each block p⁻¹(t) contains at least 3 vertices.

    The fiber {v | p v = t} is precisely the vertex set of the component E⁻¹(t), because p v = t if and only if [v] = E⁻¹(t). Its cardinality is at least 3 by the minimum component size established earlier.

    lines 61–69

    uses SimpleGraph.ConnectedComponent.mem_supp_iff

      have hpmin : ∀ t, 3 ≤ ((Finset.univ : Finset (Fin n)).filter fun v => p v = t).card := by
        intro t
        have he : ((Finset.univ : Finset (Fin n)).filter fun v => p v = t) = (E.symm t).supp.toFinset := by
          ext v
          simp only [Finset.mem_filter,Finset.mem_univ,true_and,Set.mem_toFinset,SimpleGraph.ConnectedComponent.mem_supp_iff]
          change E (G.connectedComponentMk v) = t ↔ G.connectedComponentMk v = E.symm t
          exact E.apply_eq_iff_eq_symm_apply
        rw [he]
        exact hmin _
  8. Every color crosses every nontrivial block cut, completing the existential witness.

    We assemble the witnesses p and r. To show that every used color crosses every nontrivial cut S, we invoke `wild_block_cut_of_color_connecting`. Its condition requires that any edge in W connects vertices in the same block: if {u, v} ∈ W with u ≠ v, then u and v are adjacent in G, so they belong to the same component, which gives p u = p v.

    lines 70–74

    uses wild_block_cut_of_color_connecting, congrArg, SimpleGraph.ConnectedComponent.connectedComponentMk_eq_of_adj, SimpleGraph.fromEdgeSet_adj

      refine ⟨p,r,hr,hpmin,?_⟩
      apply wild_block_cut_of_color_connecting c W hW p r hr
      intro u v huv hw
      apply congrArg E
      exact SimpleGraph.ConnectedComponent.connectedComponentMk_eq_of_adj ((SimpleGraph.fromEdgeSet_adj (↑W : Set (Sym2 (Fin n)))).2 ⟨Finset.mem_coe.2 hw,huv⟩)
SimpleGraph.fromEdgeSet
Constructs the simple graph on a given vertex type with edges given by a set of pairs, omitting self-loops.
wild_odd_color_connecting_closed_block_card_ge_three
In an odd-order (n ≥ 3) complete graph, any nonempty vertex subset closed under edges of a color-connecting set W has size at least 3.
SimpleGraph.fromEdgeSet_adj
Two distinct vertices are adjacent in `SimpleGraph.fromEdgeSet s` if and only if their pair belongs to s.
Finset.card_eq_sum_card_fiberwise
The size of a finite set equals the sum of the sizes of the fibers of any map defined on it.
Finset.sum_le_sum
If f(i) ≤ g(i) for all elements i of a finite set, then the sum of f over the set is at most the sum of g.
Finset.card_le_card
A subset of a finite set has cardinality at most that of the superset.
simple_graph_card_vertices_le_edges_add_components
In any finite graph, the number of vertices is at most the number of edges plus the number of connected components.
Nat.card_eq_fintype_card
For any finite type, its cardinality as a natural number (`Nat.card`) equals its `Fintype.card`.
Fintype.equivFinOfCardEq
A finite type with cardinality m is equivalent (in bijection) with Fin m.
congrArg
Applying a function to equal arguments produces equal results.
SimpleGraph.ConnectedComponent.mem_supp_iff
A vertex belongs to the support of a connected component if and only if the component is its equivalence class.
wild_block_cut_of_color_connecting
If W is a color-connecting set and every edge in W connects vertices in the same block of a rooted partition, then every color crosses every nontrivial block cut.
SimpleGraph.ConnectedComponent.connectedComponentMk_eq_of_adj
Adjacent vertices belong to the same connected component.

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_odd_optimal_color_connecting_partition {n k : ℕ} (hn : 3 ≤ n) (hodd : n%2=1)    (c : (⊤ : SimpleGraph (Fin n)).lineGraph.Coloring (Fin k))    (W : Finset (Sym2 (Fin n)))    (hW : simple_graph_is_color_connecting (⊤ : SimpleGraph (Fin n)) c ↑W)    (hcard : W.card = n-n/3) :    ∃ (p : Fin n → Fin (n/3)) (r : Fin (n/3) → Fin n),      (∀ t, p (r t) = t) ∧      (∀ t, 3 ≤ ((Finset.univ : Finset (Fin n)).filter fun v => p v = t).card) ∧      (∀ (e : (⊤ : SimpleGraph (Fin n)).edgeSet) (S : Finset (Fin (n/3))),        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  let G : SimpleGraph (Fin n) := SimpleGraph.fromEdgeSet (↑W : Set (Sym2 (Fin n)))  have hmin : ∀ C : G.ConnectedComponent, 3 ≤ C.supp.toFinset.card := by    intro C    apply wild_odd_color_connecting_closed_block_card_ge_three hn hodd c W hW C.supp.toFinset    · exact ⟨C.out,Set.mem_toFinset.2 C.out_eq⟩    · intro u v huv hu hv hw      have hadj : G.Adj u v := (SimpleGraph.fromEdgeSet_adj (↑W : Set (Sym2 (Fin n)))).2 ⟨Finset.mem_coe.2 hw,huv⟩      apply hv      exact Set.mem_toFinset.2 ((C.mem_supp_congr_adj hadj).1 (Set.mem_toFinset.1 hu))  have hsumV : (∑ C : G.ConnectedComponent, C.supp.toFinset.card) = n := by    have hi := Finset.card_eq_sum_card_fiberwise (f := G.connectedComponentMk)      (s := (Finset.univ : Finset (Fin n))) (t := (Finset.univ : Finset G.ConnectedComponent))      (fun _ _ => Finset.mem_univ _)    have hA : ∀ C : G.ConnectedComponent, C.supp.toFinset = Finset.univ.filter (fun v => G.connectedComponentMk v = C) := by      intro C      ext v      simp only [Set.mem_toFinset,SimpleGraph.ConnectedComponent.mem_supp_iff,Finset.mem_filter,Finset.mem_univ,true_and]    simp_rw [hA]    simpa only [Finset.card_univ,Fintype.card_fin] using hi.symm  have hcmin : 3 * Fintype.card G.ConnectedComponent ≤ n := by    have hi := Finset.sum_le_sum (fun C (_ : C ∈ (Finset.univ : Finset G.ConnectedComponent)) => hmin C)    simp only [hsumV,Finset.sum_const,Finset.card_univ,nsmul_eq_mul,mul_comm] at hi    exact_mod_cast hi  have hEdges : G.edgeFinset.card ≤ W.card := by    apply Finset.card_le_card    intro e he    have he' : e ∈ G.edgeSet := SimpleGraph.mem_edgeFinset.1 he    exact (SimpleGraph.edgeSet_fromEdgeSet (↑W : Set (Sym2 (Fin n))) ▸ he').1  have hcmax : n ≤ Nat.card G.edgeSet + Nat.card G.ConnectedComponent := by    have hi := simple_graph_card_vertices_le_edges_add_components G    simpa only [SimpleGraph.edgeFinset_card, ← Nat.card_eq_fintype_card,Nat.card_fin] using hi  have hcmin' : 3 * Nat.card G.ConnectedComponent ≤ n := by    simpa only [← Nat.card_eq_fintype_card] using hcmin  have hEdges' : Nat.card G.edgeSet ≤ W.card := by    simpa only [SimpleGraph.edgeFinset_card, ← Nat.card_eq_fintype_card] using hEdges  have hcc' : Nat.card G.ConnectedComponent = n/3 := by omega  have hcc : Fintype.card G.ConnectedComponent = n/3 := by simpa only [Nat.card_eq_fintype_card] using hcc'   let E : G.ConnectedComponent ≃ Fin (n/3) := Fintype.equivFinOfCardEq hcc  let p : Fin n → Fin (n/3) := fun v => E (G.connectedComponentMk v)  let r : Fin (n/3) → Fin n := fun t => (E.symm t).out  have hr : ∀ t, p (r t) = t := by    intro t    change E (G.connectedComponentMk ((E.symm t).out)) = t    exact (congrArg E (E.symm t).out_eq).trans (E.apply_symm_apply t)  have hpmin : ∀ t, 3 ≤ ((Finset.univ : Finset (Fin n)).filter fun v => p v = t).card := by    intro t    have he : ((Finset.univ : Finset (Fin n)).filter fun v => p v = t) = (E.symm t).supp.toFinset := by      ext v      simp only [Finset.mem_filter,Finset.mem_univ,true_and,Set.mem_toFinset,SimpleGraph.ConnectedComponent.mem_supp_iff]      change E (G.connectedComponentMk v) = t ↔ G.connectedComponentMk v = E.symm t      exact E.apply_eq_iff_eq_symm_apply    rw [he]    exact hmin _  refine ⟨p,r,hr,hpmin,?_⟩  apply wild_block_cut_of_color_connecting c W hW p r hr  intro u v huv hw  apply congrArg E  exact SimpleGraph.ConnectedComponent.connectedComponentMk_eq_of_adj ((SimpleGraph.fromEdgeSet_adj (↑W : Set (Sym2 (Fin n)))).2 ⟨Finset.mem_coe.2 hw,huv⟩)
See it in the graphDiscuss this resultChallenge it