```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, basedon quasi's theorem:``Suppose G is a finite unit distance graph such thatchi(G) = 5.Furthermore, suppose that any proper induced subgraphH of G has chi(H) < 5.cf.:http://en.wikipedia.org/wiki/Glossary_of_graph_theory#SubgraphsThen 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-vis "properly known as" the induced subgraph of Ginduced by V\{v}, where V is the vertex-set of G.So the proper induced subgraph convenientlydenoted 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 havedeg(v) >=4.  qed.Broadly speaking, a finite unit distance graphG with chi(G)=5 which has the minimum possiblenumber of vertices must have deg(v)>=4 forany vertex v of G.David Bernier-- Let us all be paranoid. More so than no such agence, Bolon Yokte K'uhwilling.
```