The Math Forum



Search All of the Math Forum:

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


Math Forum » Discussions » sci.math.* » sci.math

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

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
quasi

Posts: 12,062
Registered: 7/15/05
Re: cotpi 69 - Black and white plane
Posted: Oct 6, 2013 5:23 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

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.

quasi


Date Subject Author
10/2/13
Read cotpi 69 - Black and white plane
cotpi
10/2/13
Read Re: cotpi 69 - Black and white plane
Pubkeybreaker
10/2/13
Read Re: cotpi 69 - Black and white plane
quasi
10/2/13
Read Re: cotpi 69 - Black and white plane
Mike Terry
10/6/13
Read Re: cotpi 69 - Black and white plane
David Bernier
10/6/13
Read Re: cotpi 69 - Black and white plane
David Bernier
10/6/13
Read Re: cotpi 69 - Black and white plane
David Bernier
10/6/13
Read Re: cotpi 69 - Black and white plane
David Bernier
10/6/13
Read Re: cotpi 69 - Black and white plane
David Bernier
10/6/13
Read Re: cotpi 69 - Black and white plane
quasi
10/6/13
Read Re: cotpi 69 - Black and white plane
quasi
10/6/13
Read Re: cotpi 69 - Black and white plane
David Bernier
10/6/13
Read Re: cotpi 69 - Black and white plane
David Bernier
10/6/13
Read Re: cotpi 69 - Black and white plane
quasi
10/6/13
Read Re: cotpi 69 - Black and white plane
David Bernier
10/9/13
Read Re: cotpi 69 - Black and white plane
Phil Carmody
10/9/13
Read Re: cotpi 69 - Black and white plane
David Bernier
10/2/13
Read Re: cotpi 69 - Black and white plane
Eric Lafontaine
10/2/13
Read Re: cotpi 69 - Black and white plane
Michael F. Stemper
10/2/13
Read Re: cotpi 69 - Black and white plane
quasi
10/2/13
Read Re: cotpi 69 - Black and white plane
quasi
10/2/13
Read Re: cotpi 69 - Black and white plane
Haran Pilpel
10/2/13
Read Re: cotpi 69 - Black and white plane
quasi
10/2/13
Read Re: cotpi 69 - Black and white plane
quasi
10/2/13
Read Re: cotpi 69 - Black and white plane
Ted Schuerzinger
10/2/13
Read Re: cotpi 69 - Black and white plane
Mark Brader
10/3/13
Read Re: cotpi 69 - Black and white plane
William Elliot

Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© The Math Forum at NCTM 1994-2017. All Rights Reserved.