quasi
Posts:
11,066
Registered:
7/15/05


Re: cotpi 69  Black and white plane
Posted:
Oct 6, 2013 1:56 PM


David Bernier wrote:
>Suppose we are looking for finite plane pointconfigurations >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 unitdistance 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) < n1 then chi(Gv) = n.
proof:
Assume the hypothesis.
Since Gv is a subgraph of G, chi(GV) <= n
Suppose chi(Gv) < n.
Choose some such coloring of Gv. Now color G the same way, leaving vertex v temporarily uncolored.
Case 1: chi(G) <= n2.
Then we can color v with an entrirely new color (not one of the ones used for Gv), which would imply chi(G) <= n1, contrary to chi(G) = n.
Case 2: chi(G) = n1
Since deg(v) < n1, there are at most n2 vertices of G which are adjacent to v, hence at most n2 colors are used for those vertices. It follows that of the n1 colors used to color Gv, at least one of those colors is still available to color v. But that meaans chi(G) <= n1, contrary to chi(G) = n.
It follows that chi(G) = n, as was to be shown.
quasi

