quasi
Posts:
12,067
Registered:
7/15/05


Re: cotpi 69  Black and white plane
Posted:
Oct 6, 2013 5:23 PM


David Bernier wrote: >David Bernier wrote: >>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 > . > >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

