Do you have a reference for this anywhere? I'm fascinated by the notion of being able to correlate the creation of certain types of proteins to the falsity of the four color theorem, and I'd really like to see how they did it.

When you add a third territory, you appear to have two choices. You may put the new territory either to one side of the dumbbell, or you may put it above or below. These though will turn out to be the same.

For the first case, place the third territory centered above the dumbell such that the three territories form an equallateral triangle. Draw in the remaining two sides of the triangle, which now represent the borders between this new territory and the first two territories. Note that had you placed the new territory below the dumbbell instead of above it, then you would produce an upside-down triangle which would function as a map identically to being rightside-up.

In the second case, slide the dumbbell over to the left and place the third territory to the right of the dumbbell such that the left side and right side territories are equally as far from the center territory. Draw a line from the new territory to the center territory, representing the border between them. Now draw a curved line between the two outside territories that passes under the center territory without touching it. All three territories now border each other.

Get out a hammer and torch and heat the two straight lines. Then beat the two outside territories with the hammer, driving them down below the horizontal position of the center territory. The two straight lines now angle down and to the sides from the center, and the curve of the bottom line is more exaggerated. Keep hammering until the angle between the two straight lines at the center territory is 60 degrees. Now straighten out the bottom curved line between the two outside territories; it will not touch the center one. You now have another equallateral triangle with circular territories at the corners, which is identical to the first case.

Ready for territory number four?

__________________
http://members.elirion.net/~maddad
There are ten kinds of people. Those that understand binary, and those that do not.

At this point we should be confident that we have a diagram representing every possible arrangement of three territories on a limited two dimensional surface. If you have lost this orientation during the building, then let me know so that we can all be on the same page.

__________________
http://members.elirion.net/~maddad
There are ten kinds of people. Those that understand binary, and those that do not.

This is a mathematically rigorous proof?

Can we just stipulate that all planar graphs of 4 nodes are four-colorable and move on from there to all remaining planar graphs?

__________________
0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 ...

Maddad, have you studied graph theory? You are describing edges and veritices, specifically the complete graph of 3 vertices, K3 (the 3 is subscript). It is a planar praph, meaning that it can be redrawn in a way so that no edges cross.

A complete graph means that every vertex is connected to every other vertex with exactly one edge.

I'm not sure where you're going with this yet, but K4 (complete graph with 4 vertices) is also planar, but K5 is not planar.

If you haven't studied graph theory, I think you would enjoy it, and I suggest you pick up any standard introduction to the subject (Bondy and Murty is a standard as I recall)

Pete

Edit: The graphs you have describes in case 1 and 2 are called isomorphic, and I don't think it is necessary to distinguish them, especially in terms of graph theory. An edge is only defined by it's associated vertices, not length, curvature, etc...

__________________
PJE

There's so much I don't know about astrophysics. I wish I had read that book by that wheelchair guy.

01101001.....(I had to check that I got your name right about 4 times!)

In terms of planar graphs/colouring and in graph theory terms, what exactly are we trying to prove?

Pete

__________________
PJE

There's so much I don't know about astrophysics. I wish I had read that book by that wheelchair guy.

The four colour theorem. Sshhh, it's going to get interesting soon. I think he's going to add a fourth vertex and join it to the other three.

Yes, please. You're welcome to move a little faster, if you'd like. I can always ask you to slow down when things get complicated.

That is not quite true. For instance, one could have three territories side by side. The graph would have three circles in a row, joined by just two lines.

I have a feeling that that is not going to make a difference in your proof, but who knows?

Don't all the territories need to be connected to each other? In that case, the three side by side would be connected by two lines PLUS another line connectin the outer two territories together.



For the next step, it doesn't seem to matter where you put the 4th, it is going to isolate (at least) one of the other territories from a future 5th. This is the big step, I imagine, figuring out how to place a 4th so that it doesn't isolate. I haven't been able to do it, and even though I have only been trying since last night, it is not apparent to me that it is even possible.

__________________
Hwæt! We Gardena in geardagum,
þeodcyninga, þrym gefrunon,
hu ða æþelingas ellen fremedon.

I don't think there's any specific requirement that all the territories touch each other, the arrangement Pace suggests is certainly possible. However, it's also true that, since we're trying to establish the maximum number of regions that could in principle be touching, it's pretty likely that simply choosing not to have two regions be adjacent when they could be isn't going to get you far.

If it were possible, that would of course be a counterexample to the four color theorem. I think, actually, that it's fairly easy to show that no arrangement of just five territories can have all of them touching each other. I think that most of those who think the four color theorem is false (I think there are pretty few such people, actually) think that there might be an arrangement of more than five territories which somehow forces at least five to all be touching each other.

The use of pictures is nice. Maddad, may I recommend doing the same? It will probably save you some time explaining what you mean, and making sure that we're all drawing the same pictures as we follow along at home.

It's certainly not true in real life--Virginia, North Caroliina, and South Carolina, USAn states, are connected, but Virginia does not share a border with South Carolina. As I said, it may not make a difference in the proof, but it is not true that all three have to touch the other two, even if they are all connected.
It's not possible. Or, as peter eldergill said, a complete graph on five points cannot be planar.]

Well, I am trying to be openminded about Maddad's claim. I hope he comes back and tells me where to put #4 so that I can still place #5 properly.

As far as real life, from what I know, the four color theorem doesn't really have anything to do with real life maps. I also don't see how adding verticies that don't connect to the others helps disprove the theorem (and keep it simple). Would you mind explaining?

__________________
Hwæt! We Gardena in geardagum,
þeodcyninga, þrym gefrunon,
hu ða æþelingas ellen fremedon.

No, Maddad still thinks the four color theorem is true. He just thinks that a proof using a computer is not a valid proof, and says that he has a simpler one.

By the way, I'm wrong about this:
A bit of quick reading shows that it's pretty easy to prove that you can't get five regions to all be bordering each other at the same time. However, that by itself doesn't prove the four color theorem. Why not? Well, the largest number of regions that a territory touches isn't necessarily the same as the number of colors needed for the map. For example, a ring of five regions (like the one on the left here) has no region touching more than two other regions, yet it requires three colors.

Ah! That is what I get for reading the first half and the second half of this thread at different times. Sorry. Things are a bit clearer now. Thank you Grey.

__________________
Hwæt! We Gardena in geardagum,
þeodcyninga, þrym gefrunon,
hu ða æþelingas ellen fremedon.

As Grey points out, and others have said, there is no set of five regions where all five touch each of the other four. That's easy to show. Over a hundred years ago, it was shown that even a map of a few dozen territories was insufficient to force five colors--but obviously, there are territories that don't touch each other in that map. Eventually, you do have to add territories that don't touch each other, in producing such maps.

But, as I say, I don't think that is going to make much difference in this proof.

But we already know that we may as well only consider maximal planar graphs, because if they are four-colorable, then trivially so are non-maximal ones. I'm having difficulty seeing how non-maximal ones could be crucial to any proof. But then you could say that we also know from Kempe that we might as well start with a vertex with five edges, and assume that the rest of the map is four-colorable, but this is Maddad's proof, so we should stay open minded as you say, and see where he's going. Let's hope this one doesn't take 10 years to disprove

__________________
There are 10 types of people in the world. Those who understand ternary, those who don't, and those waiting for a bus.
If logic doesn't work, then surely it does.

I don't want to try to speculate much further until we see the next step from Maddad, but there is at least one thing to consider here. It's true that we need only consider maximally connected graphs, but if we're building up the graphs by adding one vertex at a time and then establishing all legitimate connections, I think that doesn't span the space of all maximally connected graphs. That is, I'm fairly certain that there exist maximal graphs for which the removal of any single vertex will leave you a non-maximal graph, and if you were to add all possible connections to this smaller graph (to make it maximally connected), you could no longer create the original graph by the re-addition of a vertex. So a proof that builds up a graph by the addition of vertices one at a time will at least need to allow non-maximal graphs in the construction process. Does that make sense? Can someone who has done more work in graph theory confirm or deny this?

Haven't studied it yet, but I get into stuff like that as it crosses what I need. Where I'm going is to construct a diagram representative of any possible arrangement of four territories that allows you to see at a glance that you are unable to add a fifth territory in such a way that it borders all four other territories.

It is indeed quite true. Those three territories must all border the other two, so the side of the two outside ones must flow above or below the center one to meet up. After thinning the flow to lines, this becomes exactly the equallateral triangle described in my longer previous post.

Musashi is now on the right track. Thank you very much for the drawings, by the way. Yes, the territories do need to be all connected to each other. You have reduced the territories to black dots, but that works just fine. I'll run with this representation.

"For the next step, it doesn't seem to matter where you put the 4th, it is going to isolate (at least) one of the other territories from a future 5th." Bingo! You got it. You skipped though one possibility. That fourth territory could be added outside the diagram instead of inside it. How about making us one more drawing of a three territory triangle with the fourth territory added outside the diagram? I would appreciate that very much.

"This is the big step, I imagine, figuring out how to place a 4th so that it doesn't isolate. I haven't been able to do it, and even though I have only been trying since last night, it is not apparent to me that it is even possible." You're right on both counts. It's a big step, and it's not possibl