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 ]
 David Bernier Posts: 3,892 Registered: 12/13/04
Re: cotpi 69 - Black and white plane
Posted: Oct 6, 2013 6:00 PM

On 10/06/2013 06:14 PM, quasi wrote:
> David Bernier wrote:
>> David Bernier wrote:
>>> 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 > .

>>
>> I believe the quoted statement below is true, based
>> on quasi's theorem

>
> I wouldn't call it quasi's theorem.
>
> I'm sure the result is well known. Moreover, since the proof
> is really easy, I would regard it as more of an exercise than
> a theorem.

I know what you mean. That is why I put a lower-case t
in "theorem". I could change things to:
"the basic fact proved by quasi".

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

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