We will use the terminology of graph theory. Here the vertices of our main graph G are the bacteria and there is an edge between two precisely when they are friends. The degree d(v) of a vertex v of G is the number of neighbours of v. The minimum degree δ(G) of G is the smallest amongst all d(v) for vertices v of G. The chromatic number χ(G) of G 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 k be a positive integer and let G be a graph on n>k vertices with δ(G)≥1 and χ(G)=k. Suppose that merging one pair or two pairs of vertices results in a graph G′ with χ(G′)≤k−1. Then δ(G)≥k.
We establish this in a series of claims.
Claim 1. δ(G)≥k−1.
Proof. Suppose for contradiction that we have a vertex v of degree r≤k−2 and denote its neighbours by v1,...,vp. (Note that, by assumption, v has at least one neighbour.)
Suppose we merge v with vi. We denote the new vertex by v0, and we colour the obtained graph in k−1 colours. Note that at most r≤k−2 colours can appear in the set S1={v0,v1,...,vi−1,vi+1,...,vp}. Therefore we can get a (k−1)-colouring of G by assigning the colour of v0 to vi and an unused colour (from the k−1 available) to v, thus contradicting the assumption that χ(G)=k. □
So from now on we may assume that there is a vertex v of G with deg(v)=k−1, as otherwise the proof is complete. We denote its neighbours by v1,...,vk−1.
Claim 2. The set of neighbours of v induces a complete graph.
Proof of Claim 2. Suppose vivj∈/E(G). Merge v with vi, giving a next vertex w, and then merge w with vj, denoting the newest vertex by v0. Then colour the resulting graph in k−1 colours. Note that at most k−2 colours can appear in the set S2={v0,v1,…,vk−1}∖{vi,vj}. So we can get a (k−1)-colouring of G by assigning the colour of v0 to vi and vj and an unused colour (from the k−1 available) to v, thus contradicting the assumption that χ(G)=k. □
Claim 3. For every edge uw, both u and w belong in the set {v,v1,...,vk−1}.
Proof. Otherwise merge u and w and call the new vertex z. If u,w∈/{v,v1,...,vk−1} then by Claim 2 the resulting graph contains a complete graph on {v,v1,...,vk−1} and so its chromatic number is at least k, a contradiction. If one of u,w belongs in the set {v,v1,...,vk−1}, say u=vi, then the resulting graph contains a complete graph on {v,v1,...,vk−1,z}∖{vi}. This is again a contradiction. □
From Claim 3 we see that G consists of a complete set on k vertices together with n−k>0 isolated vertices. This is a contradiction as δ(G)≥1.