Maths Olympiad Prep

Library / /14 of 17

Combinatorics Difficulty 7.8 National Olympiad, round 2 Prove it Balkan Mathematical Olympiad

There is a population PP of 1000010000 bacteria, some of which are friends (friendship is mutual), so that each bacterion has at least one friend and if we wish to assign to each bacterion a coloured membrane so that no two friends have the same colour, then there is a way to do it with 20212021 colours, but not with 20202020 or less.

Two friends AA and BB can decide to merge in which case they become a single bacterion whose friends are precisely the union of friends of AA and BB. (Merging is not allowed if AA and BB are not friends.) It turns out that no matter how we perform one merge or two consecutive merges, in the resulting population it would be possible to assign 20202020 colours or less so that no two friends have the same colour. Is it true that in any such population PP every bacterium has at least 20212021 friends?

Proposed by Bulgaria

Solution

We will use the terminology of graph theory. Here the vertices of our main graph GG are the bacteria and there is an edge between two precisely when they are friends. The degree d(v)d(v) of a vertex vv of GG is the number of neighbours of vv. The minimum degree δ(G)\delta(G) of GG is the smallest amongst all d(v)d(v) for vertices vv of GG. The chromatic number χ(G)\chi(G) of GG is the number of colours needed in order to colour the vertices such that neighbouring vertices get distinct colours.
It suffices to establish the following:

Claim. Let kk be a positive integer and let GG be a graph on n>kn > k vertices with δ(G)1\delta(G) \ge 1 and χ(G)=k\chi(G) = k. Suppose that merging one pair or two pairs of vertices results in a graph GG' with χ(G)k1\chi(G') \le k - 1. Then δ(G)k\delta(G) \ge k.

We establish this in a series of claims.

Claim 1. δ(G)k1\delta(G) \ge k - 1.

Proof. Suppose for contradiction that we have a vertex vv of degree rk2r \le k - 2 and denote its neighbours by v1,...,vpv_1, ..., v_p. (Note that, by assumption, vv has at least one neighbour.)

Suppose we merge vv with viv_i. We denote the new vertex by v0v_0, and we colour the obtained graph in k1k - 1 colours. Note that at most rk2r \le k - 2 colours can appear in the set S1={v0,v1,...,vi1,vi+1,...,vp}S_1 = \{v_0, v_1, ..., v_{i-1}, v_{i+1}, ..., v_p\}. Therefore we can get a (k1)(k - 1)-colouring of GG by assigning the colour of v0v_0 to viv_i and an unused colour (from the k1k - 1 available) to vv, thus contradicting the assumption that χ(G)=k\chi(G) = k. \square

So from now on we may assume that there is a vertex vv of GG with deg(v)=k1\deg(v) = k - 1, as otherwise the proof is complete. We denote its neighbours by v1,...,vk1v_1, ..., v_{k-1}.

Claim 2. The set of neighbours of vv induces a complete graph.

Proof of Claim 2. Suppose vivjE(G)v_i v_j \notin E(G). Merge vv with viv_i, giving a next vertex ww, and then merge ww with vjv_j, denoting the newest vertex by v0v_0. Then colour the resulting graph in k1k-1 colours. Note that at most k2k-2 colours can appear in the set S2={v0,v1,,vk1}{vi,vj}S_2 = \{v_0, v_1, \dots, v_{k-1}\} \setminus \{v_i, v_j\}. So we can get a (k1)(k-1)-colouring of GG by assigning the colour of v0v_0 to viv_i and vjv_j and an unused colour (from the k1k-1 available) to vv, thus contradicting the assumption that χ(G)=k\chi(G) = k. \square

Claim 3. For every edge uwuw, both uu and ww belong in the set {v,v1,...,vk1}\{v, v_1, ..., v_{k-1}\}.

Proof. Otherwise merge uu and ww and call the new vertex zz. If u,w{v,v1,...,vk1}u, w \notin \{v, v_1, ..., v_{k-1}\} then by Claim 2 the resulting graph contains a complete graph on {v,v1,...,vk1}\{v, v_1, ..., v_{k-1}\} and so its chromatic number is at least kk, a contradiction. If one of u,wu, w belongs in the set {v,v1,...,vk1}\{v, v_1, ..., v_{k-1}\}, say u=viu = v_i, then the resulting graph contains a complete graph on {v,v1,...,vk1,z}{vi}\{v, v_1, ..., v_{k-1}, z\} \setminus \{v_i\}. This is again a contradiction. \square

From Claim 3 we see that GG consists of a complete set on kk vertices together with nk>0n-k > 0 isolated vertices. This is a contradiction as δ(G)1\delta(G) \ge 1.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.