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 test
a 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 clear
to all) means that the graph G can be colored with
n colors, but can't be colored with less than n
colors.

Similarly, deg(v) stands for the degree of a vertex v
of 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'uh
willing.