International Mathematical Olympiad Shortlisted Problems

Let us consider a graph with the imons as vertices, and two imons being connected if and only if they are entangled. Recall that a proper coloring of a graph $G$ is a coloring of its vertices in several colors so that every two connected vertices have different colors.

Lemma. Assume that a graph $G$ admits a proper coloring in $n$ colors $(n>1)$. Then one may perform a sequence of operations resulting in a graph which admits a proper coloring in $n-1$ colors.

Proof. Let us apply repeatedly operation (i) to any appropriate vertices while it is possible. Since the number of vertices decreases, this process finally results in a graph where all the degrees are even. Surely this graph also admits a proper coloring in $n$ colors $1,\dots ,n$; let us fix this coloring.

Now apply the operation (ii) to this graph. A proper coloring of the resulting graph in $n$ colors still exists: one may preserve the colors of the original vertices and color the vertex $I^{\prime }$ in a color $k+1(\mathrm{mod}n)$ if the vertex $I$ has color $k$. Then two connected original vertices still have different colors, and so do their two connected copies. On the other hand, the vertices $I$ and $I^{\prime }$ have different colors since $n>1$.

All the degrees of the vertices in the resulting graph are odd, so one may apply operation (i) to delete consecutively all the vertices of color $n$ one by one; no two of them are connected by an edge, so their degrees do not change during the process. Thus, we obtain a graph admitting a proper coloring in $n-1$ colors, as required. The lemma is proved.

Now, assume that a graph $G$ has $n$ vertices; then it admits a proper coloring in $n$ colors. Applying repeatedly the lemma we finally obtain a graph admitting a proper coloring in one color, that is - a graph with no edges, as required.

---

Alternative solution.

Again, we will use the graph language.

I. We start with the following observation. Lemma. Assume that a graph $G$ contains an isolated vertex $A$, and a graph $G^{\circ }$ is obtained from $G$ by deleting this vertex. Then, if one can apply a sequence of operations which makes a graph with no edges from $G^{\circ }$, then such a sequence also exists for $G$.

Proof. Consider any operation applicable to $G^{\circ }$ resulting in a graph $G_1^{\circ }$; then there exists a sequence of operations applicable to $G$ and resulting in a graph $G_1$ differing from $G_1^{\circ }$ by an addition of an isolated vertex $A$. Indeed, if this operation is of type (i), then one may simply repeat it in $G$. Otherwise, the operation is of type (ii), and one may apply it to $G$ and then delete the vertex $A^{\prime }$ (it will have degree 1). Thus one may change the process for $G^{\circ }$ into a corresponding process for $G$ step by step. In view of this lemma, if at some moment a graph contains some isolated vertex, then we may simply delete it; let us call this operation (iii).

II. Let $V=\left\{A_1^0,\dots ,A_n^0\right\}$ be the vertices of the initial graph. Let us describe which graphs can appear during our operations. Assume that operation (ii) was applied $m$ times. If these were the only operations applied, then the resulting graph $G_n^m$ has the set of vertices which can be enumerated as $$V_n^m=\left\{A_i^j:1⩽i⩽n,0⩽j⩽2^m-1\right\},$$ where $A_i^0$ is the common "ancestor" of all the vertices $A_i^j$, and the binary expansion of $j$ (adjoined with some zeroes at the left to have $m$ digits) "keeps the history" of this vertex: the $d$th digit from the right is 0 if at the $d$th doubling the ancestor of $A_i^j$ was in the original part, and this digit is 1 if it was in the copy.

Next, the two vertices $A_i^j$ and $A_k^{\ell }$ in $G_n^m$ are connected with an edge exactly if either (1) $j=\ell$ and there was an edge between $A_i^0$ and $A_k^0$ (so these vertices appeared at the same application of operation (ii)); or (2) $i=k$ and the binary expansions of $j$ and $\ell$ differ in exactly one digit (so their ancestors became connected as a copy and the original vertex at some application of (ii)).

Now, if some operations (i) were applied during the process, then simply some vertices in $G_n^m$ disappeared. So, in any case the resulting graph is some induced subgraph of $G_n^m$.

III. Finally, we will show that from each (not necessarily induced) subgraph of $G_n^m$ one can obtain a graph with no vertices by applying operations (i), (ii) and (iii). We proceed by induction on $n$; the base case $n=0$ is trivial.

For the induction step, let us show how to apply several operations so as to obtain a graph containing no vertices of the form $A_n^j$ for $j\in \mathbb{Z}$. We will do this in three steps.

Step 1. We apply repeatedly operation (i) to any appropriate vertices while it is possible. In the resulting graph, all vertices have even degrees.

Step 2. Apply operation (ii) obtaining a subgraph of $G_n^{m+1}$ with all degrees being odd. In this graph, we delete one by one all the vertices $A_n^j$ where the sum of the binary digits of $j$ is even; it is possible since there are no edges between such vertices, so all their degrees remain odd. After that, we delete all isolated vertices.

Step 3. Finally, consider any remaining vertex $A_n^j$ (then the sum of digits of $j$ is odd). If its degree is odd, then we simply delete it. Otherwise, since $A_n^j$ is not isolated, we consider any vertex adjacent to it. It has the form $A_k^j$ for some $k<n$ (otherwise it would have the form $A_n^{\ell }$, where $\ell$ has an even digit sum; but any such vertex has already been deleted at Step 2). No neighbor of $A_k^j$ was deleted at Steps 2 and 3, so it has an odd degree. Then we successively delete $A_k^j$ and $A_n^j$.

Notice that this deletion does not affect the applicability of this step to other vertices, since no two vertices $A_i^j$ and $A_k^{\ell }$ for different $j,\ell$ with odd digit sum are connected with an edge. Thus we will delete all the remaining vertices of the form $A_n^j$, obtaining a subgraph of $G_{n-1}^{m+1}$. The application of the induction hypothesis finishes the proof.