Kvant Math Problem 893

Verified: no
Verdicts: SKIP + SKIP
Solve time: 12m10s
Source on kvant.digital

Problem

Every two of the $n$ computer units are connected by a wire. Is it possible to color each of these wires with one of $n-1$ colors so that $n-1$ wires of different colors leave each unit, if

$n=6$;
$n=13$?

V. B. Alekseev

Moscow Mathematical Olympiad (1984)

Exploration

The complete graph on $n$ vertices is $K_n$. The condition says that every vertex is incident with exactly one edge of each of the $n-1$ colors. Since each vertex has degree $n-1$, this means that for every color, each vertex is incident with exactly one edge of that color.

Fix a color. The edges of that color form a spanning subgraph in which every vertex has degree $1$. Such a graph is a perfect matching. Hence each color class must be a perfect matching of $K_n$.

This immediately gives a necessary condition. A perfect matching exists only when $n$ is even. Therefore if such a coloring exists, then $n$ must be even.

For $n=13$, which is odd, this already suggests impossibility.

For $n=6$, we need a construction. Since each color class must be a perfect matching, the problem becomes: can the edges of $K_6$ be partitioned into $5$ perfect matchings?

The number of edges of $K_6$ is $15$. A perfect matching on $6$ vertices contains $3$ edges. Five perfect matchings contain $15$ edges altogether, exactly the number needed. Thus it suffices to exhibit five pairwise disjoint perfect matchings.

Label the vertices by $0,1,2,3,4,5$. Arrange $0,1,2,3,4$ on a cycle and keep $5$ in the center. For each $i\in{0,1,2,3,4}$, take the matching

$${5i,\ (i+1)(i+4),\ (i+2)(i+3)},$$

with indices modulo $5$.

Writing them out gives

$${50,14,23},$$

$${51,20,34},$$

$${52,31,40},$$

$${53,42,01},$$

$${54,03,12}.$$

These are five perfect matchings and together they contain all $15$ edges.

The only delicate point is proving rigorously that every color class must be a perfect matching. Once that is established, the odd case is impossible and the even case reduces to a standard one factorization of $K_6$.

Problem Understanding

We are given the complete graph $K_n$, whose vertices represent computer units and whose edges represent wires. We must color every edge with one of $n-1$ colors so that at every vertex the $n-1$ incident edges have pairwise different colors.

This is a Type D problem. We must determine whether such a coloring exists for $n=6$ and for $n=13$, constructing it when it exists and proving impossibility when it does not.

The core difficulty is translating the local condition at each vertex into a global structural condition on each color class. The crucial observation is that every color class must be a perfect matching.

The answer is that the coloring exists for $n=6$ and does not exist for $n=13$. The intuitive reason is that each color must pair up all vertices, which is possible only when the number of vertices is even.

Proof Architecture

First, prove that for any color, every vertex is incident with exactly one edge of that color.

Next, deduce that the edges of any fixed color form a perfect matching of $K_n$.

Then show that a perfect matching cannot exist when $n$ is odd, yielding impossibility for $n=13$.

Finally, construct five pairwise disjoint perfect matchings of $K_6$ whose union is the entire edge set, and assign a different color to each matching.

The most delicate lemma is the second one, because the entire argument depends on correctly deriving the structure of a color class from the vertex condition.

Solution

Let the colors be denoted by $1,2,\dots,n-1$.

Assume that a required coloring exists. Fix a color $c$.

Every vertex of $K_n$ has degree $n-1$. By hypothesis, the $n-1$ edges incident with any vertex have pairwise different colors. Since there are exactly $n-1$ available colors, each color appears exactly once among the edges incident with that vertex. In particular, every vertex is incident with exactly one edge of color $c$.

Consider the subgraph consisting of all edges of color $c$. Every vertex has degree $1$ in this subgraph. A graph in which every vertex has degree $1$ is a disjoint union of edges. Since all vertices are present and each has degree $1$, the color-$c$ subgraph is a perfect matching.

Thus every color class must be a perfect matching.

For $n=13$, this is impossible. A perfect matching partitions the vertex set into pairs, so it can exist only when the number of vertices is even. Since $13$ is odd, no perfect matching of $K_{13}$ exists. Hence the required coloring does not exist for $n=13$.

Now consider $n=6$.

Label the vertices by $0,1,2,3,4,5$. Define five sets of edges:

$$M_0={50,14,23},$$

$$M_1={51,20,34},$$

$$M_2={52,31,40},$$

$$M_3={53,42,01},$$

$$M_4={54,03,12}.$$

Each $M_i$ consists of three pairwise disjoint edges and covers all six vertices. Hence each $M_i$ is a perfect matching.

The graph $K_6$ has

$$\binom{6}{2}=15$$

edges. The five matchings contain

$$5\cdot 3=15$$

edges altogether.

The edge incident with vertex $5$ in $M_i$ is $5i$, so the five matchings contain all five edges adjacent to vertex $5$ exactly once.

The remaining ten edges join pairs of vertices from ${0,1,2,3,4}$. These are precisely

$$01,02,03,04,12,13,14,23,24,34.$$

Inspecting the matchings shows that each of these ten edges occurs exactly once:

$$14,23;\quad 20,34;\quad 31,40;\quad 42,01;\quad 03,12.$$

Therefore the matchings are pairwise disjoint and their union is the entire edge set of $K_6$.

Assign color $i$ to all edges of $M_i$ for $i=0,1,2,3,4$. Since each $M_i$ is a perfect matching, every vertex is incident with exactly one edge of color $i$. Consequently, at every vertex the five incident edges have five different colors.

This coloring satisfies all requirements.

Hence a required coloring exists for $n=6$ and does not exist for $n=13$.

$$\boxed{\text{Possible for }n=6,\ \text{impossible for }n=13.}$$

Verification of Key Steps

The first delicate step is proving that each color appears exactly once at every vertex. A vertex is incident with $n-1$ edges, and there are $n-1$ colors. The condition says the incident edges have pairwise different colors. Since exactly $n-1$ distinct colors are used on $n-1$ edges and only $n-1$ colors exist, every color must occur once. The argument would fail if there were more available colors than incident edges, but here the numbers are equal.

The second delicate step is identifying a color class as a perfect matching. From the previous step, every vertex has degree $1$ in the subgraph formed by a fixed color. Any connected component of a graph all of whose vertices have degree $1$ is a single edge. Hence the entire subgraph is a disjoint union of edges covering all vertices, which is exactly a perfect matching.

The third delicate step is checking that the five matchings for $K_6$ cover every edge exactly once. The five edges incident with vertex $5$ appear once each as $50,51,52,53,54$. The remaining ten edges among ${0,1,2,3,4}$ are

$$01,02,03,04,12,13,14,23,24,34,$$

and each appears in exactly one of the displayed matchings. Since the total number of listed edges is $15$, equal to the number of edges of $K_6$, no edge is omitted and none is repeated.

Alternative Approaches

A more general approach uses the theory of one factorizations of complete graphs. The required coloring is exactly a decomposition of $K_n$ into $n-1$ perfect matchings. Such a decomposition exists for every even $n$ and for no odd $n$. Applying this theorem immediately yields existence for $n=6$ and nonexistence for $n=13$.

The direct approach above is preferable because it proves the necessary structural fact from the statement itself and then gives an explicit coloring for $K_6$. No external theorem is required, and every step can be verified from first principles.