There is a population P of 10000 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 2021
colours, but not with 2020 or less.
Two friends A and B can decide to merge in which case they become a single bacterion whose
friends are precisely the union of friends of A and B. (Merging is not allowed if A and B 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 2020 colours or less so that no two
friends have the same colour. Is it true that in any such population P every bacterium has at
least 2021 friends?
Balkanshortlist2021combinatoricscolouringgraph