Date: Oct 6, 2013 4:59 PM Author: David Bernier Subject: Re: cotpi 69 - Black and white plane On 10/06/2013 04:13 PM, David Bernier wrote:

> 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 > .

The kinds of graphs being considered are known as

'unit distance graphs', cf.:

< http://en.wikipedia.org/wiki/Unit_distance_graph > .

I believe the quoted statement below is true, based

on quasi's theorem:

``Suppose G is a finite unit distance graph such that

chi(G) = 5.

Furthermore, suppose that any proper induced subgraph

H of G has chi(H) < 5.

cf.:

http://en.wikipedia.org/wiki/Glossary_of_graph_theory#Subgraphs

Then any vertex v of G has the property: deg(v) >= 4."

Proof:

If not, then for some vertex v of G, deg(v) < 4.

By quasi's theorem, chi(G-v) = 5. Note: the subgraph G-v

is "properly known as" the induced subgraph of G

induced by V\{v}, where V is the vertex-set of G.

So the proper induced subgraph conveniently

denoted G-v is such that chi(G-v) = 5.

This contradicts the assumption that:

any proper induced subgraph H of G has chi(H) < 5.

Therefore, if v is a vertex of G, one must have

deg(v) >=4. qed.

Broadly speaking, a finite unit distance graph

G with chi(G)=5 which has the minimum possible

number of vertices must have deg(v)>=4 for

any vertex v of G.

David Bernier

--

Let us all be paranoid. More so than no such agence, Bolon Yokte K'uh

willing.