From: rusin@vesuvius.math.niu.edu (Dave Rusin) Subject: Re: 4 color theorem Date: 25 Feb 1999 06:23:51 GMT Newsgroups: sci.math Keywords: Not the same as non-planarity of K5 Ken Tucker wrote: >Four Colored Map Problem. February 16, 1999. [...] >Since it is impossible to connect all 5 dots with each other, we will >never need 5 colors. By analogy, I suppose you would say this: if we have a graph in which no set of four vertices are all mutually connected, then the graph can be colored with 4 colors. Is that right? Certainly a set of four mutually connected dots _does_ force the use of four colors, and "the converse is clear". At least, your bald statement quoted here seems to imply that the only reason to require N colors would be to have N mutually connected dots. So how 'bout it: is that converse clear or not? Is it possible to need N colors in a graph which never has N mutually connected dots? . . . . . . SPOILER . . . V1 / | \ / | \ / | \ V5---V0---V2 | / \ | | / \ | V4-------V3 No set of four vertices is mutually connected, but four colors are needed anyway. Clearly V0 has to be a different color from the other V_i, so if you thought you didn't need four colors you'd have to color the other five vertices with just two colors; a parity argument forbids this. This is the kind of thing one has to prove in the 4CT: that a graph which requires 5 colors or more would have to contain a set of five mutually-connected dots OR some other configuration of dots, analogous to the six-vertex pattern shown above which prevents 3-colorability. Then you have to observe that NONE of those configurations ever occurs in a graph which can be embedded in the plane. Well, I know how to characterize those graphs which can occur in the plane, but getting a complete list of the configurations which require five colors is another matter. For starters, there's the 7-vertex graph obtained by adding a vertex V6 to the graph shown above, with V6 connected to all the others. It doesn't contain a set of 5 mutually connected dots, but it requires 5 colors anyway. I can prove _this_ one cannot occur in any planar graph. But what other configurations are there to worry about? Hmm? Guess the problem's not so easy after all. dave ============================================================================== From: mathwft@math.canterbury.ac.nz (Bill Taylor) Subject: Re: 4 color theorem Date: 27 Feb 1999 03:50:29 GMT Newsgroups: sci.math rusin@vesuvius.math.niu.edu (Dave Rusin) writes: |> V1 |> / | \ |> / | \ |> / | \ |> V5---V0---V2 |> | / \ | |> | / \ | |> V4-------V3 |> |> No set of four vertices is mutually connected, but four colors are needed My standard example for showing in class, which will be familiar to most readers here, is where V0 is Nevada, V4 California, V3 Arizona, and so on. This has the added advantage that I can leave it on the board, and just a few minutes later extend the same pic 2 states to show four regions meeting at a point; (to remark that non-adjacents like Arizona and Colorado may be equi-colored). There are no places in the world where four countries meet at a point, though Zimbabwe, Zambia, Namibia, and Botswana miss out by only a silvery thread, (Zam & Bot have a 100-yd common border of river). Interestingly though, there are four cases of *constellations* meeting at a point, including the "Cat's Corner" of Leo, Leo minor, Lynx and Cancer (so what's *that* doing in a catty place!?) Zimbabwe, in fact, means "Lion-land", so there's obviously something weirdly territorial about cats in general. Maybe Zambia means the same? New Zealand (rah!) used to have the only place in the world where FIVE (5) counties met at a point. Though I still have an old map of it, the rotten bureaucrats went and changed it all some while ago, so now we don't. (sniff) -------------------------------------------------------------------------- * * *---* N.Z. graph theory is... |\ | / SELF-COMPLEMENTARY ! | \ | / <---------------------------~~~~~~~~~~~~~~~~~~ | \| / * * *---* Bill Taylor W.Taylor@math.canterbury.ac.nz --------------------------------------------------------------------------