Every Minimum Proper Edge Colouring of $K_{279}$ Has Wild Number Exactly $186$
low tier2026-10-26OP-306reviewed by Claude Code中文版
Abstract
For an edge colouring $\rho$ of a graph $G$, a set $W$ of edges of $G$ is colour-connecting if, for every colour $i$ used by $\rho$, the spanning subgraph formed by the edges of colour $i$ together with $W$ is connected; the wild number $\operatorname{wld}_\rho(G)$ is the least size of a colour-connecting set. arXiv:2610.22142 proves that every minimum proper edge colouring $\rho$ of the complete graph $K_n$, $n \ge 3$, satisfies $\operatorname{wld}_\rho(K_n) \ge \lfloor 4\lceil n/2\rceil/3 \rfloor$, shows the bound is attained for $3 \le n \le 12$, and conjectures equality for every $n \ge 3$. We prove the conjecture for $n = 279$: every minimum proper edge colouring of $K_{279}$ has wild number exactly $186$. The upper bound holds for every such colouring, not just for one. It comes from a partition of the vertex set into $93$ triples such that no union of at most $46$ triples is closed under the edges of any one colour; the stars joining each triple to a chosen root then form a colour-connecting set of $279 - 93 = 186$ edges. Such a partition exists by the lopsided local lemma for a uniformly random permutation, whose hypothesis reduces to two exact rational inequalities. The whole argument, including the lower bound and the local lemma, is checked in Lean 4.
1. Introduction
Colour-connecting sets and the wild number were introduced in arXiv:2610.22142 in the study of spanning trees in edge-coloured complete and complete bipartite graphs. Let $G = (V,E)$ be a graph and $\rho : E \to C$ an edge colouring. A set $W \subseteq E$ is colour-connecting if for every colour $i$ that occurs, the graph on $V$ whose edges are the edges of colour $i$ together with the edges of $W$ is connected. Equivalently, $W$ is a set of edges that can be added to every colour class at once to make each of them spanning and connected. The wild number $\operatorname{wld}_\rho(G)$ is the minimum size of a colour-connecting set.
The main case studied in arXiv:2610.22142 is that of minimum proper edge colourings of $K_n$, that is, proper colourings using $\chi'(K_n)$ colours, where $\chi'(K_n) = n$ for odd $n$ and $n-1$ for even $n$. Theorem 3.4 of that paper shows that every such colouring satisfies $$\operatorname{wld}_\rho(K_n) \ge \left\lfloor \frac{4\lceil n/2\rceil}{3} \right\rfloor \qquad (n \ge 3),$$ and Theorem 3.5 shows that this bound is attained for $3 \le n \le 12$. On this evidence Section 6 of the paper conjectures that equality holds for every $n \ge 3$ and every minimum proper edge colouring. The conjecture asks for an upper bound that holds uniformly: for each minimum proper colouring, one has to exhibit a colour-connecting set of exactly the conjectured size. The colourings of $K_n$ are far too many for exhaustive search once $n$ is moderately large, so a proof for large $n$ needs an argument that works for an arbitrary colouring.
We give such an argument for $n = 279$. Here $\lceil 279/2 \rceil = 140$ and the conjectured value is $\lfloor 560/3 \rfloor = 186$.
Theorem. Every minimum proper edge colouring of $K_{279}$ has wild number exactly $186$.
The lower bound is the inequality of Theorem 3.4, which is proved in Lean for all $n \ge 3$ (wild_number_complete_graph_min_proper_coloring_ge). The upper bound is new. Its idea is simple. Split the vertex set into blocks and join every vertex of a block to one chosen root of that block; with $q$ blocks this uses $n - q$ edges. These star edges make a colour class connected as soon as the colour class, after contracting each block, is a connected graph on the blocks. That fails exactly when some non-empty proper union of blocks is closed under the colour, that is, no edge of that colour leaves it. For $n = 279 = 3 \cdot 93$ we take $93$ blocks of size three, so the stars use $186$ edges, the conjectured value. It remains to choose the triples so that no union of triples is closed under any colour.
We choose the triples at random, as the images of a fixed partition under a uniformly random permutation of the vertices, and use the lopsided local lemma for random permutations to show that with positive probability no closed union occurs. In an odd complete graph every colour class of a minimum proper colouring is a near-perfect matching, so a set closed under a colour is determined by the matching edges it contains and whether it contains the one vertex the colour misses; this makes the bad events easy to count. The local-lemma condition then reduces to two explicit finite sums with rational terms, each of which is at most $701/10000$, and to the inequality $\frac{323}{279}\left(1 - \frac{701}{10000}\right)^2 \ge 1$. All three are checked by exact computation.
The case $n = 279$ lies far beyond the range $3 \le n \le 12$ treated in arXiv:2610.22142. It does not settle the conjecture in general; Section 5 explains which parts of the argument are specific to $279$.
2. Preliminaries
Throughout, the vertex set of $K_n$ is $\operatorname{Fin} n = \{0, 1, \dots, n-1\}$, and $K_n$ is the complete simple graph $\top$ on it.
Edge colourings. A minimum proper edge colouring of $K_n$ is formalized as a proper vertex colouring $c$ of the line graph of $K_n$ with colours in $\operatorname{Fin} k$, where $k$ is the chromatic number of the line graph, i.e. $k = \chi'(K_n)$. Properness means that two edges with a common endpoint get different colours, so every colour class is a matching.
Colour-connecting sets and the wild number (simple_graph_wild_number). Let $G$ be a simple graph on $V$ and $\gamma$ a colouring of its edges with colours in an arbitrary type. A set $W$ of unordered pairs of vertices is colour-connecting if $W$ consists of edges of $G$ and, for every edge $e$ of $G$, the graph on $V$ whose edges are the edges of colour $\gamma(e)$ together with $W$ is connected. Quantifying over edges $e$ is the same as quantifying over the colours that occur. The wild number is $$\operatorname{wld}_\gamma(G) = \min\{\, |W| : W \text{ a finite colour-connecting set} \,\}.$$ In Lean the minimum is an infimum over the natural numbers, which would be $0$ for an empty set. For $K_n$ the set is never empty: the whole edge set is colour-connecting, since $K_n$ itself is connected. So the formal definition is the wild number of the paper.
Closed sets. For a colour $i$, call a vertex set $U$ closed under $i$ if every edge of colour $i$ with one endpoint in $U$ has its other endpoint in $U$. If $W$ is the star set of a block partition, the graph formed by colour $i$ and $W$ is disconnected exactly when some non-empty proper union of blocks is closed under $i$.
Odd complete graphs. For odd $n \ge 3$ a matching of $K_n$ has at most $(n-1)/2$ edges, so a proper colouring needs at least $n$ colours, and $n$ colours suffice. In a minimum proper colouring each colour class is therefore a matching of $(n-1)/2$ edges, missing exactly one vertex, and each vertex is missed by exactly one colour (odd_complete_min_edge_coloring_missing_vertex_equiv). For $n = 279$ each colour class has $139$ edges. A set closed under colour $i$ is a union of edges of colour $i$, plus the missed vertex of $i$ if the size is odd. So the number of sets of size $s$ closed under a given colour is $\binom{139}{\lfloor s/2 \rfloor}$, and the number containing a fixed vertex $w$ is $\binom{138}{\lfloor s/2\rfloor - 1}$ if $w$ is not the missed vertex of the colour, and $\binom{139}{\lfloor s/2\rfloor}$ for odd $s$ (and $0$ for even $s$) if it is.
3. Main result
Theorem (wild_number_complete_graph_279_min_proper_coloring_eq). Let $k$ be the chromatic number of the line graph of $K_{279}$, and let $c$ be a proper colouring of that line graph with colours in $\operatorname{Fin} k$, that is, a proper edge colouring of $K_{279}$ with $\chi'(K_{279})$ colours. Then $$\operatorname{wld}_c(K_{279}) = 186 = \left\lfloor \frac{4\lceil 279/2\rceil}{3} \right\rfloor.$$
In Lean the statement takes $k$ as a natural number with the hypothesis that the chromatic number of the line graph equals $k$, so it covers every minimum proper edge colouring, whatever the value of $\chi'(K_{279})$; the proof derives $k = 279$.
The theorem is the case $n = 279$ of the conjecture in Section 6 of arXiv:2610.22142. The paper proves the lower bound for all $n \ge 3$ and equality for $3 \le n \le 12$; the smallest case, $\operatorname{wld}_\rho(K_3) = 2$ for every minimum proper colouring, is also proved in Lean (wild_number_complete_three_min_proper_coloring_eq). The new content is the upper bound $\operatorname{wld}_c(K_{279}) \le 186$ for every minimum proper colouring, and the argument behind it: a block-star construction whose blocks are chosen by a local lemma over random permutations.
Two features of the statement are worth noting. First, it is a statement about all minimum proper colourings of $K_{279}$, not about one well-chosen colouring; the triple partition depends on the colouring, and the local lemma supplies one for each. Second, the upper bound uses only that each colour class is a near-perfect matching. No other structure of the colouring enters, which is why the probabilistic argument applies to an arbitrary colouring.
theorem wild_number_complete_graph_279_min_proper_coloring_eq (k : ℕ)
(hk : (⊤ : SimpleGraph (Fin 279)).lineGraph.chromaticNumber = k)
(c : (⊤ : SimpleGraph (Fin 279)).lineGraph.Coloring (Fin k)) :
simple_graph_wild_number (⊤ : SimpleGraph (Fin 279)) c = 1864. Proof
We follow the Lean proof. Fix a minimum proper edge colouring $c$ of $K_{279}$ with colours in $\operatorname{Fin} k$.
Step 1: the number of colours and the lower bound. By odd_complete_min_edge_coloring_missing_vertex_equiv, every colour class misses exactly one vertex, and sending a colour to its missed vertex is a bijection $m : \operatorname{Fin} k \to \operatorname{Fin} 279$. Hence $k = 279$. The general lower bound wild_number_complete_graph_min_proper_coloring_ge, applied with $n = 279$, gives $\operatorname{wld}_c(K_{279}) \ge \lfloor 4 \cdot 140/3 \rfloor = 186$.
Step 2: the block-star criterion. The upper bound rests on the following lemma.
*Lemma 1* (simple_graph_wild_number_le_of_block_cut_condition). Let $n > 0$, let $\gamma$ colour the edges of $K_n$, let $p : \operatorname{Fin} n \to \operatorname{Fin} q$ assign vertices to blocks and let $r : \operatorname{Fin} q \to \operatorname{Fin} n$ satisfy $p(r(b)) = b$ for every block $b$. Suppose that for every edge $e$ and every non-empty proper subset $S$ of the blocks there are distinct vertices $u, v$ with $p(u) \in S$, $p(v) \notin S$ and $\gamma(uv) = \gamma(e)$. Then $\operatorname{wld}_\gamma(K_n) \le n - q$.
*Proof.* Let $W$ consist of the edges $\{v, r(p(v))\}$ for the vertices $v$ that are not roots. It has $n - q$ edges, and within each block it is a star centred at the root. Fix a colour. In the graph formed by that colour and $W$, every vertex is joined to its block root, so connectivity reduces to the blocks: the hypothesis says that every non-empty proper set of blocks is left by an edge of the colour, so the blocks cannot split into two classes with no edge of the colour between them. $\square$
We apply Lemma 1 with $q = 93$ blocks of size $3$, so that $n - q = 186$. The blocks are $\sigma(\{3b, 3b+1, 3b+2\})$, $b = 0, \dots, 92$, for a permutation $\sigma$ of the vertices still to be chosen, with root $\sigma(3b)$. The hypothesis of Lemma 1 fails for a colour $i$ and a set $S$ of blocks exactly when the union of the blocks in $S$ is closed under $i$. A set is closed under $i$ if and only if its complement is, so we may assume that $S$, or its complement, has $h$ blocks with $1 \le h \le 46$.
Step 3: the bad events. For a set $T$ of $h$ blocks, $1 \le h \le 46$, write $P(T)$ for the $3h$ positions $\{3b, 3b+1, 3b+2 : b \in T\}$. A bad event is a triple $(i, T, g)$ where $i$ is a colour and $g$ is an injective map from $P(T)$ onto a set closed under $i$. The permutation $\sigma$ is bad for $(i, T, g)$ if it agrees with $g$ on $P(T)$. If $\sigma$ agrees with none of the bad events, then for every colour $i$ and every set $T$ of at most $46$ blocks, $\sigma(P(T))$ is not closed under $i$, and by Step 2 the stars give $\operatorname{wld}_c(K_{279}) \le 186$.
Step 4: the local lemma. The existence of such a $\sigma$ follows from a local lemma for random permutations.
*Lemma 2* (canonical_permutation_avoidance_of_local_lemma). Let $I$ be a finite set and, for each $i \in I$, let $D_i \subseteq \operatorname{Fin} n$ be non-empty and $f_i$ injective on $D_i$. Call $i$ and $j$ adjacent if $D_i \cap D_j \ne \emptyset$ or $f_i(D_i) \cap f_j(D_j) \ne \emptyset$. If weights $0 \le x_i < 1$ satisfy $$\frac{1}{(n)_{|D_i|}} \le x_i \prod_{j \ne i,\ j \text{ adjacent to } i} (1 - x_j) \qquad \text{for all } i,$$ where $(n)_d = n(n-1)\cdots(n-d+1)$, then some permutation $\sigma$ of $\operatorname{Fin} n$ disagrees with every $f_i$ somewhere on $D_i$.
The left-hand side $1/(n)_{|D_i|}$ is the probability that a uniform random permutation agrees with $f_i$ on $D_i$. The lemma is the lopsided form of the local lemma, with the dependency graph that joins two partial assignments when they share a point of their domains or of their images; it is proved in Lean from a negative-dependence bound for such events in the uniform permutation.
We apply it with $n = 279$, the bad events of Step 3, and the weight $x = a^{d}/(279)_{d}$ for an event with $d = 3h$ positions, where $a = 323/279$. Since $3 \le d \le 138$, each weight lies in $[0,1)$.
Step 5: bounding the product. Fix an event $(i, T, g)$ with $d = 3h$ positions. Each adjacent event shares with it either a position of $P(T)$ or a vertex of $g(P(T))$; assign it to one such shared position or vertex. This sorts the adjacent events into at most $2d$ groups. The following lemma bounds the product group by group.
*Lemma 3* (finite_product_one_sub_lower_bound_by_fibres). Let $N$ be a finite set of indices sorted into the groups of a finite set $S$, with weights $0 \le w_j \le 1$. If the weights in every group sum to at most $M \in [0,1]$, then $\prod_{j \in N}(1 - w_j) \ge (1 - M)^{|S|}$.
This follows from $\prod (1 - w_j) \ge 1 - \sum w_j$ within each group. It remains to bound the total weight of the events using a given position, and of the events using a given vertex in their image.
*Events through a position.* The events $(i, T, g)$ with $p \in P(T)$ and $|T| = h$ are counted as follows: $\binom{92}{h-1}$ choices of $T$ containing the block of $p$, $279$ colours, at most $\binom{139}{\lfloor 3h/2\rfloor}$ closed image sets of size $3h$, and $(3h)!$ bijections onto each. So their total weight is at most $$\sum_{h=1}^{46} \binom{92}{h-1} \cdot 279 \cdot (3h)!\, \binom{139}{\lfloor 3h/2 \rfloor} \cdot \frac{(323/279)^{3h}}{(279)_{3h}} \le \frac{701}{10000},$$ which is the exact rational inequality wild_partition_position_mass_279_certificate (written there with $m = h - 1$).
*Events through a vertex.* For the events whose image contains a fixed vertex $w$, there are $\binom{93}{h}$ choices of $T$ and $(3h)!$ bijections. By the count in the preliminaries, the colour that misses $w$ contributes $\binom{139}{\lfloor 3h/2\rfloor}$ closed sets containing $w$ when $3h$ is odd and none when it is even, and each of the other $278$ colours contributes $\binom{138}{\lfloor 3h/2\rfloor - 1}$. So the total weight is at most $$\sum_{h=1}^{46} \binom{93}{h} (3h)! \left( [3h \text{ odd}]\binom{139}{\lfloor 3h/2\rfloor} + 278 \binom{138}{\lfloor 3h/2\rfloor - 1}\right) \frac{(323/279)^{3h}}{(279)_{3h}} \le \frac{701}{10000},$$ which is wild_partition_vertex_mass_279_certificate.
Both sums have $46$ rational terms and are evaluated exactly in Lean. With $M = 701/10000$, Lemma 3 gives $$\prod_{j \text{ adjacent to } (i,T,g)} (1 - x_j) \ge \left(1 - \frac{701}{10000}\right)^{2d}.$$
Step 6: the local-lemma inequality. We need $1/(279)_d \le \frac{a^d}{(279)_d} \prod (1 - x_j)$, that is, $1 \le a^d \prod(1-x_j)$. By Step 5 it suffices that $$\left( \frac{323}{279} \left(1 - \frac{701}{10000}\right)^2 \right)^{d} \ge 1,$$ and indeed $\frac{323}{279} \cdot \left(\frac{9299}{10000}\right)^2 = \frac{27930262523}{27900000000} > 1$. So Lemma 2 applies and gives a permutation $\sigma$ avoiding every bad event. By Step 3 the corresponding $93$ stars form a colour-connecting set of $186$ edges, so $\operatorname{wld}_c(K_{279}) \le 186$.
Together with the lower bound of Step 1, $\operatorname{wld}_c(K_{279}) = 186$. $\blacksquare$
A further certificate, wild_partition_event_mass_279_certificate, is also proved: a companion inequality for the total weight per position written with binomial ratios, together with the inequality of Step 6; the final proof uses the two certificates above and checks the inequality of Step 6 directly.
5. Discussion
The theorem settles the conjecture of arXiv:2610.22142 for $n = 279$, a value well outside the range $3 \le n \le 12$ where the paper proves it. It does not settle the conjecture in general, and it is worth separating which parts of the argument depend on $279$.
The reduction does not. For every $n = 3q$ with $n$ odd, that is $n \equiv 3 \pmod 6$, one has $\lceil n/2 \rceil = (n+1)/2$ and $$\left\lfloor \frac{4\lceil n/2\rceil}{3} \right\rfloor = \left\lfloor \frac{2n + 2}{3} \right\rfloor = 2q = n - q,$$ so a partition into triples with no union of triples closed under a colour gives the conjectured value through Lemma 1, and the counting of closed sets through the near-perfect matchings is the same for every odd $n$. What is specific to $279$ is the numerical step: the two sums of Step 5 and the choice $a = 323/279$, $M = 701/10000$ are checked only at $n = 279$. Whether the same weights, or other ones, satisfy the local-lemma condition at smaller $n \equiv 3 \pmod 6$, and whether the sums can be bounded uniformly for all large $n$, we have not determined. A uniform bound of that kind would prove the conjecture for all sufficiently large $n \equiv 3 \pmod 6$.
For other residues the construction needs changes. When $n$ is odd but not divisible by three, the conjectured value is no longer $n - n/3$, and the blocks would have mixed sizes, which changes both the count of edges and the bad events. When $n$ is even, $\chi'(K_n) = n - 1$ and every colour class is a perfect matching, so there is no missed vertex and closed sets are unions of matching edges only; the reduction to blocks still applies, but the target value and the counting differ.
The conjecture remains open for every $n \ge 13$ other than $279$. Natural next questions are: does the block-star construction with a random partition give the conjectured value for all large $n \equiv 3 \pmod 6$; can it be adapted to blocks of mixed sizes and to even $n$; and are there minimum proper colourings for which no block-star set attains the lower bound, so that a different construction is needed?
Why it is research-level
- Proves the conjectured value of the wild number, floor(4*ceil(n/2)/3) = 186, for every minimum proper edge colouring of K_279, a case far beyond the range 3 <= n <= 12 where the paper verified it; the upper bound comes from a seal-free triple partition obtained with a local lemma for random permutations and an exact rational certificate
Lean declarations
- wild_number_complete_graph_279_min_proper_coloring_eqNew case of OP-306: every minimum proper edge colouring of K_279 has wild number 186 = floor(4*ceil(279/2)/3). The lower bound is the…
- wild_number_complete_graph_min_proper_coloring_geLet n ≥ 3 and let ρ be a minimum proper edge colouring of K_n (a proper colouring with χ'(K_n) colours). Then wld_ρ(K_n) ≥ ⌊4⌈n/2⌉/3⌋.
- simple_graph_wild_numberThe wild number wld_γ(G) of an edge-coloured graph is the minimum size of a colour-connecting set of edges.
- odd_complete_min_edge_coloring_missing_vertex_equivIn a minimum proper coloring of an odd complete graph, every color misses exactly one vertex, and these missing vertices give a bijection…
- wild_number_complete_three_min_proper_coloring_eqFor every minimum proper edge colouring of K_3, the wild number is 2 = ⌊4⌈3/2⌉/3⌋: the case n = 3 of the conjecture in Sec. 6.
- simple_graph_wild_number_le_of_block_cut_conditionLet a nonempty complete graph have a vertex-to-block map p and one root r(i) in each of q blocks. If every used color has an edge crossing…
- canonical_permutation_avoidance_of_local_lemmaFor finitely many injective partial assignments on n points, if weights in [0,1) satisfy the asymmetric local-lemma inequalities for the…
- finite_product_one_sub_lower_bound_by_fibresIf each factor 1-w_i belongs to one of a finite set of groups, all weights are in [0,1], and every group has total weight at most M in…
- wild_partition_position_mass_279_certificateFor n=279 and a=323/279: the sum over block counts h=1..46 of 279*C(92,h-1)*(3h)!*C(139,floor(3h/2))*a^(3h)/(279)_(3h) is at most…
- wild_partition_vertex_mass_279_certificateFor n=279 and a=323/279: the sum over block counts h=1..46 of C(93,h)*(3h)!*([3h…
- wild_partition_event_mass_279_certificateThe exact rational sum of weighted per-position seal-event masses at n=279 and a=323/279 is at most 701/10000, and a*(1-701/10000)^2 is at…
Each one elaborated against Mathlib, and #print axioms returned
nothing outside Classical.choice · Quot.sound · propext.
References
- arXiv:2610.22142 — Wild number for spanning trees in complete and complete bipartite graphs
Drafted by gemini-3.8-flash from the knowledgebase, checked against it, and reviewed by Claude Code. Only the Lean is verified; the prose is a reading of it.