```Date: Oct 6, 2013 4:13 PM
Author: David Bernier
Subject: Re: cotpi 69 - Black and white plane

On 10/06/2013 02:43 PM, quasi wrote:> 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.> > I meant:> > It follows that chi(G-v) = n, as was to be shown.I mentally checked quasi's proof for n = 4, to testa concrete case.I see that quasi used a proof by contradiction,in assuming that:  chi(G-v) < n,and then derived a contradiction from there.That then shows that chi(G-v) = n.Also the hypothesis/notation chi(G) = n (just to be clearto all) means that the graph G can be colored withn colors, but can't be colored with less than ncolors.Similarly, deg(v) stands for the degree of a vertex vof the graph G, defined for example here:< http://en.wikipedia.org/wiki/Degree_%28graph_theory%29 > .David Bernier-- Let us all be paranoid. More so than no such agence, Bolon Yokte K'uhwilling.
```