Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: cotpi 69 - Black and white plane
Replies: 26   Last Post: Oct 9, 2013 10:23 AM

 Messages: [ Previous | Next ]
 quasi Posts: 12,067 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 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.

quasi

Date Subject Author
10/2/13 cotpi
10/2/13 Pubkeybreaker
10/2/13 quasi
10/2/13 Mike Terry
10/6/13 David Bernier
10/6/13 David Bernier
10/6/13 David Bernier
10/6/13 David Bernier
10/6/13 David Bernier
10/6/13 quasi
10/6/13 quasi
10/6/13 David Bernier
10/6/13 David Bernier
10/6/13 quasi
10/6/13 David Bernier
10/9/13 Phil Carmody
10/9/13 David Bernier
10/2/13 Eric Lafontaine
10/2/13 Michael F. Stemper
10/2/13 quasi
10/2/13 quasi
10/2/13 Haran Pilpel
10/2/13 quasi
10/2/13 quasi
10/2/13 Ted Schuerzinger