Place a fourth dot in a random position on the paper and join it to the other three by random lines subject to the three constraints mentioned above.
Place a fifth dot in a random position on the paper. You will find that you can connect it to three of the other dots but not the fourth if you stick to the three constraints.
If you now imagine that the dots relate to areas of different colour, each line relates to a change in colour, i.e. it crosses a shared border. The experiment infers, therefore, that given any five areas of the paper, you can colour them with four colours; the fifth will not share a border with more than three other areas requiring a change of colour. This can be extended to any group of four or five areas.
I don’t see your point GB. Just because a small graph can be four colored does not imply that all planar graphs can. (Although the colorability of a small collection of graphs was key to the original proof. It was first proven that the cases were enough to prove it true for any number.) There are a lot of proofs of color requirements for higher genuses (doughnuts with holes) that require a lot more verices than the actual number of colors required.
An example is not a proof in this case.
Secondly, for “higer dimensions” there is no bound on colorability outside of the number of nodes. I.e., a complete graph of 100 nodes can be embedded in three space and requires 100 colors.
Furthermore, the fact that five points cannot be mutually interconnected in a plane has been known for a long time. Indeed, it has been known for a long time that all impossible graphs on a plane can be simplified to one of two forms: five mutual connections, or connections from all of three points to all of three other points (the old “jealous utilities” puzzle). But that doesn’t prove the four-color theorem. For that matter, playing with dots on paper doesn’t constitute a proof.
Here’s an example of the degree of rigor required. One of the basic theorems of topology is the Jordan Curve Theorem, which states that any closed curve (a curve that eventually meets itself at its beginning) divides a plane into an inside and an outside. Yes. Someone had to prove that. And it’s not as easy as you think.
I’m not sure what he means about the 3-D case. It is possible to mutually link any number of points in more than two dimensions – at least, as long as the number of points is less than aleph-1.
This was an example of the effect of the 4-colour map theorem.
Thanks to DuckDuckGoose for pointing out to what it refers.
It isn’t a proof in so far as it does not offer anything beyond five points as a general case: there may be combinations of say three hundred points within which grouping into numbers of these cases is not possible, though I have so far found none.
However, I am glad to see that someone has a proof (which I haven’t been able to do myself) that this is indeed is the basic case of all “impossible graphs”. In their association there may be a “proof” of the 4-colour theorem available.
The 3-D version refers to connecting N points on a surface (dimension N-1) of a dimension N object. Experimentation seems to indicate that the maximum number of points (and maybe by extension, colours necessary to colour in areas!) is 3N-2, though this could do with proving for higher dimensions.
Again, it’s an experimental means of visualisation. It ought not to be despised, as the computer proof took an experimental point (the existence of chains of two colours) and experimentally ran through the cases.
What does “map” mean in this instance? Is it an abstract mathemtacial concept or does it refer to a specific type of map as understood by cartographers (e.g. political world map)?
Experimentation? You’ve been doing this in four dimensions, have you?
For a (3D) sphere, its surface is equivalent to the 2D map case–just pop a hole in the middle of any of the spherical countries and spread it out on a flat map.
For a (3D) torus, it is well known that the answer is seven. That was proved a long time ago, and it is easy to visualize. Just paint stripes on a donut, so they go through the hole. Cut a line around the equator of the donut, and shift everything two and a half stripes width over. Each country will touch all six other countries. So, that works for 3N-2, with N=3.
But it doesn’t work for surfaces of other 3D objects. Just take a sphere with any number of countries. Patch a tube from each country through the interior of the sphere to each of the other countries. Then, all countries will share a border with all the others.
If you have an N dim. space and an N-1 dimensional surface, if N-1 is 3 or more, you are in 3 space, see my earlier post. Graph coloring is only interesting on 2d surfaces. The main parameter is genus, how many holes there are in the doughnut.
