# The possible partition into some parts

Solution IMO 2015 (combinatoric shortlist )

**Problem 7:**

In a company of people some pairs are enemies. A group of people is called unsociable if the number of members in the group is odd and at least 3, and it is possible to arrange all its members around a round table so that every two neighbours are enemies. Given that there are at most 2015 unsociable groups, prove that it is possible to partition the company into 11 parts so that no two enemies are in the same part.

Also Read:

Solution 1.

Let G = (V, E) be a graph where V is the set of people in the company and E is the set of the enemy pairs — the edges of the graph. In this language, partitioning into 11 disjoint enemy-free subsets means properly coloring the vertices of this graph with 11 colors.

We will prove the following more general statement.

Claim. Let G be a graph with chromatic number . Then G contains at least 2^{k-1} – k unsociable groups.

Recall that the chromatic number of G is the least k such that a proper coloring

exists. In view of 2^{11} – 12 > 2015, the claim implies the problem statement.

Let G be a graph with chromatic number k. We say that a proper coloring (1) of G is leximinimal, if the k-tuple (|V_{1}|. |V_{2}|…..|V_{k}|) is lexicographically minimal; in other words, the following conditions are satisfied: the number n_{1} = |v_{1}| | is minimal; the number n_{2} = |v_{2}| is minimal, subject to the previously chosen value of n_{1};……: the number n_{k-1} = |v_{k-1}| is minimal, subject to the previously chosen values of n_{1},…,n_{k-2}.

The following lemma is the core of the proof.

Lemma 1.

Suppose that G = (V, E) is a graph with odd chromatic number k e 3, and let (1)

be one of its leximinimal colorings. Then G contains an odd cycle which visits all color classes v_{1}, v_{2}, …,v_{k}.

Proof of Lemma 1. Let us call a cycle colorful if it visits all color classes. Due to the deﬁnition of the chromatic number, V_{1} is nonempty. Choose an arbitrary vertex . We construct a colorful odd cycle that has only one vertex in V_{1}, and this vertex is v.

We draw a subgraph of G as follows. Place v in the center, and arrange the sets V_{2, }V_{3}, …, V_{k} in counterclockwise circular order around it. For convenience, let V_{k+1} = V_{2}. We will draw arrows to add direction to some edges of G, and mark the vertices these arrows point to. First we draw arrows from v to all its neighbors in V_{i+1}, and mark all those neighbors. If some vertex with {2, 3, . . ., k} is already marked, we draw arrows from u to all its neighbours in V_{i+1} which are not marked yet, and we mark all of them. We proceed doing this as long as it is possible. The process of marking is exempliﬁed in Figure 1.

Notice that by the rules of our process, in the ﬁnal state, marked vertices in V_{i} cannot have unmarked neighbors in V_{i+1}. Moreover, v is connected to all marked vertices by directed paths.

Now move each marked vertex to the next color class in circular order (see an example in Figure 3). In view of the arguments above, the obtained coloring is proper. Notice that v has a neighbor , because otherwise

would be a proper coloring lexicographically smaller than (1). If w was unmarked, i.e., w was an element of V_{2}, then it would be marked at the beginning of the process and thus moved to V_{3}, which did not happen. Therefore, w is marked and .

Since w is marked, there exists a directed path from v to w. This path moves through the sets V_{2},…,V_{k} in circular order, so the number of edges in it is divisible by k – 1 and thus even. Closing this path by the edge , we get a colorfull odd cycle, as required.

Proof of the claim. Let us choose a leximinimal coloring (1) of G. For every set {1,2,..,k} such that |C| is odd and greater than 1, we will provide an odd cycle visiting exactly those color classes whose indices are listed in the set C. This property ensures that we have different cycles for different choices of C, and it proves the claim because there are 2^{k-1} – k choices for the set C.

Let , and let G_{C} be the induced subgraph of G on the vertex set V_{c}. We also have the induced coloring of V_{c} with |C| colors; this coloring is of course proper. Notice further that the induced coloring is leximinimal: if we had a lexicographically smaller coloring of G_{c}, then these classes, together the original color classes V_{i} for , would provide a proper coloring which is lexicographically smaller than (1). Hence Lemma 1, applied to the subgraph G_{c} and its leximinimal coloring , provides an odd cycle that visits exactly those color classes that are listed in the set C.

**Also Read : Combinatoric Shortlist Problem in IMO 2015**