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.