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: