[Math] Proof that every map produces a planar graph – Four Colour Theorem

coloringgraph theoryplanar-graphs

I was watching this Youtube video:

https://www.youtube.com/watch?v=NgbK43jB4rQ

At around the 6 minute mark, it's mentioned that the $K_5$ doesn't produce a valid map. I'm guessing it has something to do with the graph being nonplanar.

So I wanted to prove that all maps produce a planar graph.

Here's my attempt

Proof by induction.

Base case: A map with just one area, produces a planar graph.

Inductive Hypothesis: Assume that any map with N areas produces a planar graph.

Inductive Step: Uses inductive hypothesis to prove that any graph with N+1 area will also produce a planar graph.

Since any graph with N area produces a planar graph, then no graph with N areas has a subgraph that is isomorphic to $K_5$ or $K_{3,3}$. So we have to show that in the worst case scenario, where our graph has a subgraph that's 1 vertex away from being $K_5$ or $K_{3,3}$, that it's not possible to add a vertex to make it so. I'm having trouble at this point.

Would appreciate the help.

Thanks

Best Answer

The intuition for why maps correspond to planar graphs is that you can use a map to draw a planar representation of its graph.

(The comments are right that we need to be somewhat careful about what maps are, what kind of lines we are allowed to draw, and the difference between a graph a drawing of a graph. So to turn this intuition into a proof, we'll need to do some work once we figure out what the right definitions are.)

Start with a map (source):

map of Austria

Its graph has a vertex for every region of this map, and an edge between two vertices if and only if the two corresponding regions are adjacent. The graph must exist; we must prove that it is planar. To do this, we will construct a planar embedding of this graph.

We begin by

  1. putting a vertex in each region, and
  2. whenever two regions border each other, putting a tick mark somewhere along the border.

Austria with vertices and tick marks

(Mathematically, the vertices and the tick marks are just points chosen either from the regions or from their borders.)

Now, within each region, draw paths from the vertex to the tick marks around each border:

Austria graph

Care must be taken at this step that the paths we draw stay in the region they're at, and don't intersect each other. It's here that we need to think very carefully about our definition of what sort of regions a map is allowed to have.

The point of adding the tick marks, however, is that this step doesn't care at all about what the map looks like globally. All you have to do is to look at the regions one at a time, and draw paths from the vertex to the tick marks. We'll never have to worry about paths in one region intersecting paths in another, because all the paths we draw stay in a single region.

(You have to prove that you can avoid two paths in the same region intersecting each other. There's a number of ways to say "if there's an intersection point, we can deform the paths until there isn't", but this step is topology, not graph theory.)

At this point, you're done! We've constructed a planar embedding of the graph for our map in which no edges cross.

Related Question