
タイトル：
Eulers Formula  Intro to Algorithms

概説：

Let's take a look at Euler's formula again.

What we're going to do is prove by induction that this holds.

We can build any planar graph by iteratively adding nodes and edges.

Let's start off with the simplest thing, which is just a single node. Tada!

We can start off with just the simplest graph of alljust a node sitting on the plane all by itself,

a lonely point, and we've got one node, no edges, and one giant region around it,

and 1  0 + 1 is indeed 2.

That's our base case.

Now we proceed by induction.

Given that we're doing a proof by induction, we're going to assume that we have

some planar graph and that Euler's formula holds for that graph.

We have already that n  m + r = 2.

What we're going to do is we're going to add to this graph so that it's still planar

and see what happens to this formula.

There are two different ways that we can add to this graph.

We can add a node and an edge together, or we can add an edge between two exiting nodes.

Let's consider this first case where we had a new node and an edge between them,

and it's still a planar graph. What happens to m, n, and r?

Well, we have one new node and one new edge but the number of regions hasn't changed.

We're just jutting into some region inside or outside,

but it doesn't change the total number of regions(n + 1)  (m + 1)

these ones cancel, and we get n  m + r,

which by our inductive hypothesis we said is 2.

In that case, the formula still holds.

What about the case where we just add an edge.

One way we can add an edge is inside of some other region,

and let's look what happens in that case.

The number of nodes is unchanged. The number of edges has gone up by one.

But the number of regions has gone up by one as well.

This used to be one giant region, and it's now been split in to two regions.

Once again, these ones cancel.

Our formula still holds.

Let's just doublecheck what happens if we do something on the outside,

sort of breaking into the huge vast region around it.

Connect, say, these two nodes, what have we done?

We still have the vast region around it, but we created a new region here.

Again, the number of regions has gone up by 1.

Similarly, if we click this over the number of regions has gone up by 1.

If we add an edge without a corresponding node, the number of regions goes up by 1.

If we add an edge and a node together, the region stays the same,

but the number of nodes goes up by 1.

No matter what you do, this formula keeps holding. Pretty cool.