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.