>Suppose we are looking for finite plane point-configurations >that must use at least 4 colours. Suppose Q is such as >configuration. > >If Z is a point in the configuration Q, and Z has >two or fewer points in Q at unit-distance from Z, >then it seems to me harmless to delete the Point Z >from the configuration, meaning that >Q less Z would still need at least 4 colours. > >But is it really true? and if so, how could one >prove it?
The proof is easy.
In general, we have the following proposition:
If G is graph with chi(G) = n and v is a vertex of G with deg(v) < n-1 then chi(G-v) = n.
Assume the hypothesis.
Since G-v is a subgraph of G, chi(G-V) <= n
Suppose chi(G-v) < n.
Choose some such coloring of G-v. Now color G the same way, leaving vertex v temporarily uncolored.
Case 1: chi(G) <= n-2.
Then we can color v with an entrirely new color (not one of the ones used for G-v), which would imply chi(G) <= n-1, contrary to chi(G) = n.
Case 2: chi(G) = n-1
Since deg(v) < n-1, there are at most n-2 vertices of G which are adjacent to v, hence at most n-2 colors are used for those vertices. It follows that of the n-1 colors used to color G-v, at least one of those colors is still available to color v. But that meaans chi(G) <= n-1, contrary to chi(G) = n.