AFTD Auto-Formalizing Theoretical Domains

quadripartite_exists_wild_number_eq_of_upper_exclusion

theoremverified

If every proper 3n-edge-colouring of K_{n,n,n,n} has wild number at most 2n + 1, and some colouring has no colour-connecting set of at most 2n edges, then that colouring has wild number exactly 2n + 1.

Statement

theorem quadripartite_exists_wild_number_eq_of_upper_exclusion (n : ℕ) (hn : 3 ≤ n)
    (hU : ∀ c : (SimpleGraph.completeEquipartiteGraph 4 n).lineGraph.Coloring (Fin (3 * n)),
      simple_graph_wild_number (SimpleGraph.completeEquipartiteGraph 4 n) c ≤ 2 * n + 1)
    (hE : ∃ c : (SimpleGraph.completeEquipartiteGraph 4 n).lineGraph.Coloring (Fin (3 * n)),
      ∀ W : Finset (Sym2 (Fin 4 × Fin n)), W.card ≤ 2 * n →
        ¬ simple_graph_is_color_connecting (SimpleGraph.completeEquipartiteGraph 4 n) c ↑W) :
    ∃ c : (SimpleGraph.completeEquipartiteGraph 4 n).lineGraph.Coloring (Fin (3 * n)),
      simple_graph_wild_number (SimpleGraph.completeEquipartiteGraph 4 n) c = 2 * n + 1
Source
step towards quadripartite_minimum_coloring_max_wild_number_eq
Verified
01 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • simple_graph_is_seal_free_partitionA vertex map p : V → Fin q is a seal-free block partition for an edge colouring γ of a graph G when (i) every block {v | p v = i} induces…
  • 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…
  • simple_graph_wild_numberThe wild number wld_γ(G) of an edge-coloured graph is the minimum size of a colour-connecting set of edges.
  • simple_graph_wild_number_attainedFor any finite connected edge-colored graph, some finite color-connecting edge set has cardinality exactly its wild number.

The proof, explained

The proof establishes that a colouring $c$ guaranteed to have no colour-connecting set of size at most $2n$ achieves wild number exactly $2n + 1$. First, it proves that the complete 4-partite graph $K_{n,n,n,n}$ is connected, which ensures the existence of a finite colour-connecting set $W$ achieving the wild number of $c$. By the exclusion hypothesis, the cardinality of $W$ cannot be at most $2n$, giving the lower bound $\operatorname{wild}(c) \ge 2n + 1$. Combining this with the assumed universal upper bound $\operatorname{wild}(c) \le 2n + 1$ by partial-order antisymmetry proves that the wild number of $c$ is exactly $2n + 1$.

  1. The graph $G = K_{n,n,n,n}$ has a nonempty vertex set, reducing the proof of its connectedness to showing that any two vertices $u, v$ can reach each other.

    We abbreviate the complete 4-partite graph with parts of size $n$, $K_{n,n,n,n}$, as $G$. Because $n \ge 3 > 0$ and $4 > 0$, the vertex $(0, 0)$ exists, so the vertex set is nonempty. To establish that $G$ is connected, it suffices to prove that any two vertices $u$ and $v$ are connected by a path in $G$.

    lines 10–13

      let G := SimpleGraph.completeEquipartiteGraph 4 n
      have hconn : G.Connected := by
        have : Nonempty (Fin 4 × Fin n) := ⟨(⟨0, by omega⟩, ⟨0, by omega⟩)⟩
        refine ⟨fun u v => ?_⟩
  2. If $u$ and $v$ belong to the same partite set, they can reach each other via an intermediate vertex in a different part.

    When $u$ and $v$ lie in the same part ($u.1 = v.1$), we find an index $i \in \operatorname{Fin} 4$ distinct from $u.1$; if no such index existed, all four indices would equal $u.1$, which would imply $0 = 1$ via congr_arg Fin.val, a contradiction. Choosing $w = (i, 0)$ in this different part gives $u.1 \ne w.1$ and $w.1 \ne v.1$. By SimpleGraph.completeEquipartiteGraph_adj, $u$ is adjacent to $w$ and $w$ is adjacent to $v$. Composing these two edges shows that $u$ can reach $v$.

    lines 14–30

    uses congr_arg, Fin.val, SimpleGraph.completeEquipartiteGraph_adj

        by_cases h : u.1 = v.1
        · obtain ⟨i, hi⟩ : ∃ i : Fin 4, i ≠ u.1 := by
            by_contra! hcontra
            have h0 := hcontra ⟨0, by omega⟩
            have h1 := hcontra ⟨1, by omega⟩
            have : (⟨0, by omega⟩ : Fin 4) = ⟨1, by omega⟩ := h0.trans h1.symm
            have : (0 : ℕ) = 1 := congr_arg Fin.val this
            omega
          let w : Fin 4 × Fin n := (i, ⟨0, by omega⟩)
          have huw : G.Adj u w := by
            rw [SimpleGraph.completeEquipartiteGraph_adj]
            exact hi.symm
          have hwv : G.Adj w v := by
            rw [SimpleGraph.completeEquipartiteGraph_adj]
            rw [← h]
            exact hi
          exact (huw.reachable).trans hwv.reachable
  3. If $u$ and $v$ belong to different partite sets, they are directly adjacent, hence reachable.

    When $u.1 \ne v.1$, SimpleGraph.completeEquipartiteGraph_adj shows that $u$ and $v$ are adjacent in $G$, so $u$ immediately reaches $v$.

    lines 31–34

    uses SimpleGraph.completeEquipartiteGraph_adj

        · have hadj : G.Adj u v := by
            rw [SimpleGraph.completeEquipartiteGraph_adj]
            exact h
          exact hadj.reachable
  4. We instantiate the witness colouring $c$ from the exclusion hypothesis and note that its wild number is at most $2n + 1$.

    We unpack the exclusion hypothesis (hE) to obtain a colouring $c$ that admits no colour-connecting set of size at most $2n$, and provide $c$ as the existential witness. Applying the universal upper bound hypothesis (hU) to $c$ gives $\operatorname{wild}(G, c) \le 2n + 1$.

    lines 35–37

      obtain ⟨c, hc⟩ := hE
      use c
      have hu := hU c
  5. There exists a colour-connecting set $W$ attaining the wild number of $c$, and its size must strictly exceed $2n$.

    Because $G$ is connected, simple_graph_wild_number_attained yields a finite set of edges $W$ that is colour-connecting for $c$ and whose size equals $\operatorname{wild}(G, c)$. By the exclusion property of $c$, any colour-connecting set cannot have cardinality at most $2n$, so $|W| \le 2n$ is false.

    lines 38–41

    uses simple_graph_wild_number_attained

      obtain ⟨W, hWcard, hWconn⟩ := simple_graph_wild_number_attained G c hconn
      have hnotle : ¬ W.card ≤ 2 * n := by
        intro hle
        exact hc W hle hWconn
  6. The wild number of $c$ is at least $2n + 1$, which together with the upper bound forces equality.

    Since $|W| = \operatorname{wild}(G, c)$ and $|W| \le 2n$ is false, linear arithmetic yields $2n + 1 \le \operatorname{wild}(G, c)$. Combining this lower bound with the upper bound $\operatorname{wild}(G, c) \le 2n + 1$ using le_antisymm shows that $\operatorname{wild}(G, c) = 2n + 1$.

    lines 42–45

    uses le_antisymm

      have hgt : 2 * n + 1 ≤ simple_graph_wild_number G c := by
        rw [← hWcard]
        omega
      exact le_antisymm hu hgt
congr_arg
Applying a function to both sides of an equality preserves the equality: if $a_1 = a_2$, then $f(a_1) = f(a_2)$.
Fin.val
The underlying natural number value $\operatorname{val}(i) \in \mathbb{N}$ of an element $i \in \operatorname{Fin} n$.
SimpleGraph.completeEquipartiteGraph_adj
In a complete equipartite graph, two vertices are adjacent if and only if their first coordinates (their parts) are distinct.
simple_graph_wild_number_attained
In any connected finite graph, there exists a finite colour-connecting edge set whose cardinality achieves the wild number of the colouring.
le_antisymm
In a partial order, if $a \le b$ and $b \le a$, then $a = b$.

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

/-- The exclusion form of sharpness plus the universal upper bound yields an attaining colouring. -/theorem quadripartite_exists_wild_number_eq_of_upper_exclusion (n : ℕ) (hn : 3 ≤ n)    (hU : ∀ c : (SimpleGraph.completeEquipartiteGraph 4 n).lineGraph.Coloring (Fin (3 * n)),      simple_graph_wild_number (SimpleGraph.completeEquipartiteGraph 4 n) c ≤ 2 * n + 1)    (hE : ∃ c : (SimpleGraph.completeEquipartiteGraph 4 n).lineGraph.Coloring (Fin (3 * n)),      ∀ W : Finset (Sym2 (Fin 4 × Fin n)), W.card ≤ 2 * n →        ¬ simple_graph_is_color_connecting (SimpleGraph.completeEquipartiteGraph 4 n) c ↑W) :    ∃ c : (SimpleGraph.completeEquipartiteGraph 4 n).lineGraph.Coloring (Fin (3 * n)),      simple_graph_wild_number (SimpleGraph.completeEquipartiteGraph 4 n) c = 2 * n + 1 := by  let G := SimpleGraph.completeEquipartiteGraph 4 n  have hconn : G.Connected := by    have : Nonempty (Fin 4 × Fin n) := ⟨(⟨0, by omega⟩, ⟨0, by omega⟩)⟩    refine ⟨fun u v => ?_⟩    by_cases h : u.1 = v.1    · obtain ⟨i, hi⟩ : ∃ i : Fin 4, i ≠ u.1 := by        by_contra! hcontra        have h0 := hcontra ⟨0, by omega⟩        have h1 := hcontra ⟨1, by omega⟩        have : (⟨0, by omega⟩ : Fin 4) = ⟨1, by omega⟩ := h0.trans h1.symm        have : (0 : ℕ) = 1 := congr_arg Fin.val this        omega      let w : Fin 4 × Fin n := (i, ⟨0, by omega⟩)      have huw : G.Adj u w := by        rw [SimpleGraph.completeEquipartiteGraph_adj]        exact hi.symm      have hwv : G.Adj w v := by        rw [SimpleGraph.completeEquipartiteGraph_adj]        rw [← h]        exact hi      exact (huw.reachable).trans hwv.reachable    · have hadj : G.Adj u v := by        rw [SimpleGraph.completeEquipartiteGraph_adj]        exact h      exact hadj.reachable  obtain ⟨c, hc⟩ := hE  use c  have hu := hU c  obtain ⟨W, hWcard, hWconn⟩ := simple_graph_wild_number_attained G c hconn  have hnotle : ¬ W.card ≤ 2 * n := by    intro hle    exact hc W hle hWconn  have hgt : 2 * n + 1 ≤ simple_graph_wild_number G c := by    rw [← hWcard]    omega  exact le_antisymm hu hgt
See it in the graphDiscuss this resultChallenge it