quasi
Posts:
10,726
Registered:
7/15/05


Re: cotpi 69  Black and white plane
Posted:
Oct 6, 2013 1:56 PM


quasi wrote: >David Bernier wrote: >> >>Suppose we are looking for finite plane pointconfigurations >>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 unitdistance 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) < n1 then chi(Gv) = n. > >proof: > >Assume the hypothesis. > >Since Gv is a subgraph of G, chi(GV) <= n > >Suppose chi(Gv) < n. > >Choose some such coloring of Gv. Now color G the same way, >leaving vertex v temporarily uncolored. > >Case 1: chi(G) <= n2. > >Then we can color v with an entrirely new color (not one of >the ones used for Gv), which would imply chi(G) <= n1, >contrary to chi(G) = n. > >Case 2: chi(G) = n1 > >Since deg(v) < n1, there are at most n2 vertices of G which >are adjacent to v, hence at most n2 colors are used for those >vertices. It follows that of the n1 colors used to color Gv, >at least one of those colors is still available to color v. >But that meaans chi(G) <= n1, contrary to chi(G) = n. > >It follows that chi(G) = n, as was to be shown.
I meant:
It follows that chi(Gv) = n, as was to be shown.
quasi

