0
$\begingroup$

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

$\endgroup$
  • 3
    $\begingroup$ The problem is that "map" is not really clearly defined, so you are going to have a hard time proving it without some more care. $\endgroup$ – Thomas Andrews Mar 27 '17 at 23:40
  • 1
    $\begingroup$ How are you defining "planar graph" in this context? It sounds vaguely like you have elevated Kuratowski's theorem to a definition. $\endgroup$ – hmakholm left over Monica Mar 27 '17 at 23:48
  • $\begingroup$ @ThomasAndrews: A map is a set of areas divided by lines. An area can is said to border another area if they are separated by a line segment. $\endgroup$ – The_Questioner Mar 28 '17 at 0:23
  • $\begingroup$ @HenningMakholm: A planar graph is a graph that has no intersecting edges. Any graph that has a subgraph that's isomorphic to $K_5$ or $K_{3,3}$ can't be planar by Kuratowski's Theorem $\endgroup$ – The_Questioner Mar 28 '17 at 0:24
  • 2
    $\begingroup$ That is not a good definition of "planar graph," because a "graph" has nothing about intersections. Look up the definition of "graph" and then reconsider. A planar graph can be defined in a number of ways, but that isn't one of them. $\endgroup$ – Thomas Andrews Mar 28 '17 at 0:40
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.