quasi wrote: >David Bernier wrote: >> >>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. > >proof: > >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. > >It follows that chi(G) = n, as was to be shown.