quadripartite_exists_wild_number_eq_of_upper_exclusion
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$.
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$.
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 => ?_⟩
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$.
uses
congr_arg,Fin.val,SimpleGraph.completeEquipartiteGraph_adjby_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
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$.
uses
SimpleGraph.completeEquipartiteGraph_adj· have hadj : G.Adj u v := by rw [SimpleGraph.completeEquipartiteGraph_adj] exact h exact hadj.reachable
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$.
obtain ⟨c, hc⟩ := hE use c have hu := hU c
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.
uses
simple_graph_wild_number_attainedobtain ⟨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
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$.
uses
le_antisymmhave 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$.
- Proving that the complete 4-partite graph $K_{n,n,n,n}$ is connected occupies lines 11–34 of the proof (more than half the lines). On paper, this is an immediate observation, but formally it requires demonstrating that $\operatorname{Fin} 4$ has at least two elements to provide an intermediate vertex bridging any two vertices in the same part.
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.
/-- 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