I nice graph theory problem came into my attention. It was given at the Ukraine NMO 2020. Its solution is extremely short, but the problem is difficult in my opinion. Especially if one has not seen the idea. This problem is in fact a *Laszlo Lovasz*‘s result, published in 1966 (see [1]). Though the idea behind it is instructive and deserves attention, I hope, it’s not a trend, famous theorems in graph theory to be transformed into Olympiad problems. Another such example is problem 5 of Bulgarian NMO 2020.

Here is an outline of this blog post. I first give the mentioned problem with a short solution. Then the Lovasz’s result [1] is commented, which is more general. Finally, a result of *Borodin and Kostochka* [3] is presented which is a further generalization. One may think that there is something involved in these generalizations, that makes them more difficult to grasp. Nothing like that! They are all done the same way – applying the same idea.

**Problem (Ukraine NMO, 2020)**. Positive integers are given, such that . In some school, each student has at most friends from that school. Prove that all the students can be split into two groups in such a way that each student in has at most friends among the students in and each one in – at most friends among those in .

I prefer the straightforward graph theory interpretation.

**Problem 1**. Let be a given graph with maximum degree and be positive integers with Prove that the set of vertices can be partitioned into two subsets in such a way that the maximum degrees of the induced graphs on and are correspondingly at most and

*Proof*. For any partition of into two sets denote by the graphs induced by and by the number of edges in resp. For any such partition, consider the function

Let be a partition that minimizes We claim (where means the maximum degree of ). Indeed, suppose there is a vertex (WLOG) with In this case, note that is connected with at most vertices in Thus, . Hence, if we move the vertex from to thus obtaining new partitions then the expression will be less than , which contradicts the minimality of

I posted the problem in AoPS forum [6], one can see a solution presented there. Note that the claim also holds when one of is zero. Assume hence Take to be a maximal independent set in In this case, any vertex is connected with at least one vertex in otherwise would be larger independent set. So, and is a desired partition.

**Theorem 2 (Laszlo Lovasz 1966, [1])**. Given a graph with maximum degree and nonnegative integers with Prove that the set of the vertices of can be partitioned into sets so that the subgraph induced by has maximum degree at most

Note that in case we just get our Problem 1. Maybe, the easiest way to prove Theorem 2 is to induct on each time applying the same argument.

Another way is to consider the function (in case all are positive)

and take a partition that minimizes This claim is present as exercise 5.1.50, p.203 in the wonderful book of D. West, [5].

**Theorem 3** (Borodin and Kostochka [3]). Let be a graph and be functions, such that

Then there is a partition of inducing subgraphs such that for any and any

*Proof* (Lemma 2.1. in [4]). The case easily follows from the case by induction. For we consider the following function

Let be a partition that minimizes The same argument as used in Problem 1 shows this partition has the desired property.

The Lovasz’s result (Theorem 2) is a special case of Theorem 3 when

One may see similar results for digraphs in a paper of Noga Alon, see [7].

References.

[1] L. Lovasz, On decomposition of graphs, Stud. Sci. Math. Hung. 1 (1966), 237–238.

[2] Problem 5 of Bulgarian NMO 2020.

[3] Borodin, O.V. and Kostochka, A.V. , On an upper bound of a graph’s chromatic number, depending on the graph’s degree and density. J. Combin. Theory Ser. B 23 (1977) 247–250.

[4] https://www.tu-ilmenau.de/fileadmin/media/dma/schweser/Masterarbeit_Schweser.pdf

[5] Douglas B. West, Introduction to Graph Theory, Pearson Education, Inc. , 2002, Second edition. (p.203, exercise 5.1.50)

[6]https://artofproblemsolving.com/community/c6t309f6h2417379s1_splitting_a_graph

[7] Noga Alon, Splitting Digraphs.