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


On 10/06/2013 06:14 PM, quasi wrote: > 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.
I know what you mean. That is why I put a lowercase t in "theorem". I could change things to: "the basic fact proved by quasi".
David Bernier  Let us all be paranoid. More so than no such agence, Bolon Yokte K'uh willing.

