
Re: cotpi 69  Black and white plane
Posted:
Oct 6, 2013 4:13 PM


On 10/06/2013 02:43 PM, quasi wrote: > 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.
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(Gv) < n, and then derived a contradiction from there. That then shows that chi(Gv) = 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 > .
David Bernier
 Let us all be paranoid. More so than no such agence, Bolon Yokte K'uh willing.

