We need a chalkboard.
By the “innermost region,” do you mean what I called the “snakey region” in my post re-describing the map? (Post 9)
Here’s a picture of the map I described:
The numbers stand for regions, not colors of course.
You’re saying region 7 can be changed so that it only borders on one of the outer regions (1, 2 or 3) and yet the Second Layer will still need four colors?
Yes, that’s right. For example, connect 4 to 5 in such a way as prevents 7 from touching 1. The second layer still won’t be colorable with just the three colors from the border: if you restricted yourself to the three colors used for 1, 2, and 3, then 4, 5, and 6 would still need to use the same colors as 3, 2, and 1 respectively, leaving no possibility for 7.
Oh, wait. You aren’t necessarily restricting yourself to the three colors from the border, are you? Just restricting to four colors overall? Damn my misparsings…
Whoops. I see I was beaten to the punch.
Region 7 is E2 and touches all three border regions.
Er, that last post was in response to what Kimmy_Gibbler is no longer saying.
Yes that’s right (I think). In the picture I linked to, the Second Layer regions require, among themselves, four colors in all, due to the way they relate to the Border Layer regions. It also happens that one of the Second Layer regions touches three Border Layer regions, and that those three Border Layer regions must be shaded three different colors. I am wondering whether this (what follows “it happens that” in the previous sentence) is a necessary feature of any map in which the Second Layer regions require among themselves a total of four colors.
If it is a necessary feature, then the line of argument I had in mind when writing the OP may still go through, and the 4-color theorem can be proved for a broad range of maps. Then this particular case (the cases in which there is a region with E-index number N touching three regions with E-index number N-1 where the three must be colored different colors) can be dealt with as a special case.
And again, to reiterate, I realize it is silly to try to prove the four color theorem. I’m just entertaining myself… 
OK, I think I have a map that provides a counterexample to the lemma any map whose E2 layer requires four colors must have at least one E2 region that touches at least three differently colored border regions.
┌───────────────────┬────────┐
│ │ │
│ ┌─────────┬────┴────┐ │
│ │ │ │ │
│ ├─────────┤ │ │
│ │ │ │ │
│ │ │ │ │
├────┤ │ │ │
│ │ │ │ │
│ │ │ │ │
│ │ ├─────────┤ │
│ │ │ │ │
│ └─────────┴─────────┘ │
│ │
└────────────────────────────┘
I put it to you that the interior regions of this map will require four colors all together while no region touches three border regions, given that there are only two such regions to begin with.
Damn, I just got one too. Well, I’ll say it anyway: take region 7 in the Flickr example and draw a triangle in it, with one point on each of the outer border regions.
(This splits 7 into the triangle plus three other regions. And the result will have the property that, for every pair of E1 regions, there will be two E2 regions which touch both of them and each other. Thus, one of these will have to be colored with the new fourth color and one will have to be colored with the color of the remaining E1 region. Thus, all four colors will be used in E2. This despite the fact that there will no longer be any single region touching all the E1 regions (the triangle only touches them all at points, which doesn’t count; even if it did count, you could break the triangle into further pieces))
Man, we really should switch over into talking graph-theoretically, though; that is, using planar graphs with a distinguished “external space” node. The E-index of a node would then just be its distance from the external space node. (In your original definition, you defined E-index using line segments, but the rest of the discussion made it clear you meant to allow for arbitrary curves to the outside instead of just straight lines; that is, E1 borders the outside, E2 borders E1 but not the outside, E3 borders E2 but not E1 or the outside, etc.)
(If it’s not clear why any region could be taken to be the outside (i.e., E0), take any given map in the plane, and fold it onto the southern hemisphere of a sphere (with the northern hemisphere standing for E0). Then pick any region of your choice to stand for the new E0, and unwrap the rest of the map back onto the plane. Presto; you’ve converted the region to count as E0 from one to an arbitrary other, without disturbing any of the connectivity (i.e., graph-theoretic) properties.)
Yeah, when I said “line segments” I was just thinking about the Border regions (there, line segments work) but it failed to occur to me that you’ll need to use curves to get the E-index for regions farther in.
I’m fine with talking graph-theoretically. I wasn’t sure how to cash out the idea of a border region in those terms, to be honest–I thought about what you just said, adding an external “region,” but wasn’t sure if that was somehow screwing some technical something or other up in some way. I also figured it would be easier for a lot of people to follow the discussion if I just talked in terms of maps straightforwardly. And also, though I understand how the transformation into graph theory works, I’ve never understood how it’s supposed to make things easier to deal with. Both ways of dealing with the problem seem equally complex to me. But that’s surely because there’s a lot I don’t know.
Thanks for the examples, you two. Back to the drawing board…
You know, earlier today I was away from the internet and trying to remember whether spherical maps are also supposed to be 4-colorable. I decided they must be, based on reasoning involving a visualization similar to the one you just described. Take a sphere that’s been divided completely into regions. Now take one of those regions and designate it “the outside”. The rest of the regions taken together can be unwrapped from the sphere to form a normal map on a plane. The “outside” region can then be pasted on as a single region surrounding the planar map. And all the relevant connectivity properties of the spherical map are preserved.
It didn’t occur to me at all that this also shows that you can take any map and treat any of its regions as “the external region.” I guess I sort of realized this (though not explicitly) as recorded in the comments in my OP about how you can have internal “external” regions. But anyway, you’re right, this makes it easier for me to see how the notion of a “Border layer” and “Second layer” and so on could be used in a graph-theoretical version of the discussion.
Fourth post in a row!
So this means, right, that you could take any arbitary region on a map, and be able to color those regions bordering it with just three colors, and still have a way to color the rest of the map with four colors.
Easiness is in the eye of the beholder, I suppose, but to me, the main advantage graph theory provides is it gets rid of all the mess of irrelevant details of the embedding. All that matters is the abstract notion of regions and adjacencies between them, regardless of whether it’s embedded into the plane one way or another. The one hurdle is whether notions like “planar” and “external space” can be captured purely in terms of this abstract adjacency relation, but by Kuratowski’s theorem, the first can, and as I just mentioned, the second amounts to just picking any arbitrary node to serve as the external space. So, it works, it gets rid of the irrelevant clutter, it helps us draw on a wealth of abstract examples, and it means we don’t have to worry so much about figuring out how best to draw the pictures… Mainly, I’m always about finding the highest useful level of abstraction. For other people, other approaches may be more intuitive.
Yes. After all, just four-color the whole map; the regions bordering the selected region only use the three colors not used for the selected region.
:smack: 
Yes of course…
Right; these would correspond to having a whole set of distinguished “space” nodes, rather than just 1.