A Map Coloring Exercise

Factual Questions
1

I’m trying to come up with a map that fits the following description. I’ll give a quasi-technical description first, then a more plain-english summary.

Maps are made of regions. And finite maps on a plane have an external edge, outside of which we could say there is a single “external region”. The external region is not part of the map–it is a single region outside every region on the map.*

Each region in the map has an E-index. A region R’s E-index is defined as the smallest number of curve segments a line segment with one enpoint inside R must cross in order to have an endpoint within the map’s external region. (In other words, to have an endpoint external to the entire map.)

Some regions have an E-index of 1. These are the regions bordering the external region.

Some regions have an E-index of 2. These are the regions bordering regions of E-index 1 while not also bordering the external region.

Call the E-index 1 regions the Border regions. Call the E-index 2 regions the Second Layer regions.

Okay, here’s what I’m trying to do. I’m trying to come up with a map which satisfies the following description: No matter how you 3-color the map’s border regions**, you must use four colors in order to color the map’s Second Layer regions, if your coloring of the Border and Second Layer regions is to satisfy the constraint that no two adjacent regions have the same color.

I said I’d give a plain english version afterwards, but actually I think the above was clear, so never mind.

Why am I asking about this? I’ve been trying to prove the 4-color map theorem off and on since I was a kid, and I’m not about to let the fact that it’s already been proven stop me. If no map like the one I described can be constructed, then I think I can prove the theorem. Since it is almost certainly the case that I can’t prove it, chances are that such a map can be constructed. But my fiddling around hasn’t produced one. I was wondering how many seconds it would take for someone who is not me to produce one.

*Actually you could have “external regions” which are actually more like holes in the map, and you could have any number of these. But let’s not complicate things. Let’s just think about the big single external region that’s intuitively external rather than internal to the map.

**The truth of the 4-color map theorem guarantees that you need at most 3 colors to color in all a map’s Border regions, if your coloring is to satisfy the condition that no two adjacent regions have the same color. For if you needed four colors for these regions, then there would be map identical to this one but with a single further region surrounding these erstwhile Border regions, and that single further region would require a fifth color.

2

Map coloring is graph coloring, and if you don’t think about it that way, you’ll get bogged down in irrelevant details. Figure out how to reformulate your question in terms of graph colorings, and you’ll have a much easier time communicating with the experts.

3

I know and I know and I know. But I’m not addressing my post to experts in particular, though they’re welcome to respond as well of course.

Is there some particular way in which you think my post shows some confusion?

4

Moved MPSIMS --> GQ.

5

Surely you can just take any map that requires four colors, and just place new regions around the border, to achieve the desired counterexample? For example, draw three concentric circles, and within the innermost circle, draw three radii.

6

Place three countries on the border (colored Red, Green, Blue) and four countries in the next layer, one touching the Red & Green border countries (and therefore itself Blue), another touching the Green & Blue borders, a third touching Red & Blue. The final 7th country occupies all remaining area, touches the other six countries and therefore uses a 4th color. (You can avoid having 4 colors in the Second Layer here only by introducing a fifth color for the entire map.)

You probably saw this example already, but allow the 5th color for your purpose. Am I right so far?

7

I don’t think so, at least I don’t think it trivially follows–for even if the starting map requires four colors, only three are required on its own Border Regions. So the new map created by drawing more regions around the old map, since the new regions also will only need three colors, (since they’re the new Border Regions,) may only need those three colors as well. It might require that you recolor the previous map in some way that leads to a fourth color being necessary among the old Border Regions, but this doesn’t seem to follow trivially anyway. If it follows, it will take some further thought (or an actual construction) to show it.

8

Consider the following map:




+----------+----------+
|          |          |
|   RED    |   BLUE   |
|          |          |
+----T-----+-----T----+
|    |           |    |
|    |  YELLOW   |    |
|    |           |    |
|    L-----------J    |
|                     |
|        GREEN        |
|                     |
+---------------------+

Regions Red, Blue, and Green are border regions and require no fewer than three colors to ensure that no two adjacent border regions share the same color. Region Yellow is a second layer region and must use a color different from any of the three border regions to ensure that no adjacent region (of any kind) share a color.

The truth of the four-coloring law is preserved of course by observing that if a second map were created by adding the hitherto off-map external region to the new map, that newly added region could be colored using the same color as is used for region Yellow.

9

Yes, this does it!

Sorry I don’t have an image host or I’d draw a diagram to show it.

I was thrown off by some aspects of your description, but here’s how I’d describe what I drew:

Three regions on the outer layer, colored A B and C. Now, one region in the second layer kind of snakes around and touches each of the three outer regions–leaving space for three further regions each touching on a pair of those three regions.

Since that snakey middle region touches all three outer layer regions, it must use a fourth color D. And of the three remaining middle regions, one is touching the A region, the B region and the D region, and so much be colored C. Another is touching B C and D so must be A. And the third must be colored B because it’s touching A C and D. So the end result is, however you 3-color the outer layer, you must use a total of for colors to color the inner layer.

10

Huh? I’m confused. I thought you wanted an example where coloring the second layer requires four colors. If the second layer is a map which requires four colors… isn’t this trivially true? Perhaps I misunderstand what you are asking for (indeed, I almost certainly do). For example, the situation with three concentric circles and three radii in the innermost one… why does this not count as the sort of thing you are looking for? (There is one region in the first layer/border, and four regions in the second layer, and no matter how you color the border, you must use four colors for the second layer)

11

Yes, but I wasn’t looking for a map where the middle regions require a fourth color be used in the map, rather, I was looking for a map where the middle regions must use four colors themselves.

I wonder if a map fulfilling what I was looking for has to have a Second Layer region that borders on three differently colored Border regions, or whether there could be a map like the one I was looking for where there is no such Second Layer region.

-Kris

12

Can you tell me how to draw the radii in the innermost circle? In other words, what regions from the second layer should they border?

13

Actually, there can’t be a second layer map requiring four colors in and of itself. (It may require four colors, but only in the context of being part of some larger map.) This is because the second layer map could itself have been an outer layer map–and outer layer maps are always 3-colorable.

14

Oh, actually, I see now what my confusion was. I was taking the second-layer to be everything with an E-index of at least 2, not of exactly two. Sorry.

15

So, to restate your question:
*
A given map is composed of border (E1) regions, E2 regions, and regions with E-indices greater than 2 (call them “multiply-interior regions”). Let’s call the union of E2 regions and multiply-interior regions: interior regions.

It happens that in order to color all of the interior regions in such a way that no region shares its color with an adjacent region (whether border, E2, or multiply-interior), no fewer than four colors must be used. Does this fact imply that the border regions must use exactly three colors? (Or must use no fewer than three colors? But, of course, border regions cannot use more than three colors in light of the reductio given in the OP).
*
Does this accurately restate your question?

16

Wait, I think you rather ask: given the map described above, must there be an E2 region that abuts no fewer than three border regions?

Is that an accurate restatement of your question?

17

Wait, sorry, are you restating the question in the OP, or the later question I asked in response to the map given that I said satisfies the constraints given in the OP? (Post 11–which was a response to you, but that question I asked there was prompted by the nature of the map described by Septimus previously. Sorry if that caused some confusion.)

18

Well, what are you looking for now? Do either of my above formulations capture it?

19

Sorry! To clarify, the second question is:

Given a map in which the Second Layer regions must use a total of four colors, must it be that one of the regions in that Second Layer is adjacent to three differently colored regions in the Border Layer?

The first question (answered by Septimus) is:

Can there be a map in which the Second Layer regions must use a total of four colors?

The answer to the First question is “Yes. There can be such a map.” It happens that the map Septimus provided has a Second Layer region adjacent to three differently colored Border Layered regions, so I was wondering if that was a necssary feature of all maps like the kind I was looking for in the OP

20

It is not a necessary feature. Take septimus’s map and change it just a little bit: Have the innermost region touch one but not all of the outermost regions (while still touching all of the other second layer regions). It will still work.