A region is a submap, as in R ⊆ M.
A country, as in C ∈ M and possibly C ∈ Ri, is an atomic element of a map. The underline indicates a whole map and not a proper submap.
A graph represents a map with nodes as countries and links as borders.
Graph forms:
The unique graph of 2 regions with a common border is two nodes connected by one link.
The unique graph of 3 mutually bordering regions is a triangle.
The unique graph of 4 mutually bordering regions is a triangle subdivided into 3 triangles.
Notation:
kM2 is a map of 2 regions with a common border and its associated graph is called kG2. The k represents the kth level of expansion (see below).
kM3 and kM4 follow suit.
kMn > 4 = ∅
Preliminary remarks:
We are uninterested in any hanging chain, which is defined as a region composed of M2's, possibly linked to an kM3 or kM4 region.
It is trivial that a proof for a map without the chain suffices for one with it.
We reject pretzel holes as illegal. One would probably not be inclined to draw such a map, but one might perchance wonder about graphs which lack interior links, as follow:
It is understood that a maximally complex map of 4n countries may be subdivided into an initial R4 in more than one way. More than one carving up may also be possible for lower level R4's. These possibilities will make no difference to our proof.
Proof:
We wish to work in a fractal-like fashion, subdividing our map into a Level 1 R4. We then expand each node, and subdivide again, so that at Level 2 we have 42, or 16, nodes.
If we have proved our case for any maximally complex map, we have proved our case. That is, any non-trivial map must be a submap of some 4n map. If a paint scheme is proved for the map, then it is proved for any legal submap, since every remaining node can keep its original color.
If a map has some M3's, each is represented by a triangle with no middle node. Hence, we can simply erase a node in a G4. The case of an M2 does not occur since it implies either an external chain or an illegal pretzel hole.
Consider the graph of an R4, where each node represents a region. We call this Level 1.
For a maximally complex map of 16 countries, we expand the graph thus
The dotted lines tell us the relevant nodes can be connected by one or two links. The symmetry tells us we don't need to check any other interior linkage possibilities. By proving for the case of all dotted line links, we prove for any legal case of erased dotted links.
A paint scheme, with colors A,B,C,D, is shown.
We now step down to Level 3, focusing on one corner triangle from Level 2. We retain the paint scheme for the three corner nodes that have been "shifted" (mentally) from Level 2. That these colors are held constant is important.
The Level 2 interior node that had been painted D is now redrawn as an 3M4. The color D is "pushed down" to the center node of each of the relevant triangles (those nodes are not pictured here).
By holding the corner nodes constant -- as shown -- we can repeat the colorization algorithm down through all levels, ad infinitum. In our algorithm, we always push D to the center nodes of the bottom level triangles.
Done.
1. Not all this nomenclature is necessary for this paper, but it is helpful in keeping concepts distinct.
No comments:
Post a Comment