MathDB

There is a population

P

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?

Problem Statement