# Euler's formula for Planar Graph

I had a quite productive day yesterday when I flew from San Francisco to Tokyo,
then travelled to Nagano because I read 50 pages of my Combinatorics book during my transit.
I found one interesting theorem about planar graph so I’ll state here along with the proof:
**Euler’s formula**: If $$G=(V,E)$$ is a connected planar graph with n (≥ 1) vertices, m edges, and r regions,
then $$n-m+r=2$$.

## Proof by induction

### Basis

Consider the case $$m=0$$. In this case, n must be 1 since G is connected. With 1 vertex and no edges, there is exactly one outer region. Thus $$n-m+r=1-0+1=2$$ as desired.

### Inductive step

Assume that the statement is true for any connected planar graph with at most k edges. In other words, for any connected planar graph $$G=(V,E)$$ with n vertices $$m\le k$$, edges, and r regions, $$n-m+r=2$$. This is the inductive hypothesis.

Suppose $$G=(V,E)$$ is a connected planar graph with n vertices, $$m=k+1$$ vertices, and r regions. If G is a tree, then $$m=n-1$$ by the property of a tree. Notice that if G is a tree, then the only region is the outer region surround the tree so $$r=1$$. Thus $$n-m+r=n-(n-1)+1=2$$ as desired.

If G is not a tree, then G has a cycle. Call the cycle C. Let e be any edge in C, and consider a subgraph $${G}^{\mathrm{\prime}}=(V,E\setminus \{e\})$$ of G. $${G}^{\mathrm{\prime}}$$ must be connected because removing an edge from a cycle breaks the cycle but does not break the connectivity of the graph. Furthermore, $${G}^{\mathrm{\prime}}$$ has one fewer region than G because removing an edge merges exactly two regions into one region. Because a subgraph of a planar graph is also planar and $$|E|=m=k+1$$, $${G}^{\mathrm{\prime}}$$ is a connected planar graph with $$|E\setminus \{e\}|=k$$ edges. Thus the inductive hypothesis applies to $${G}^{\mathrm{\prime}}$$ and yields $$n-k+(r-1)=2$$. Therefore, $$n-m+r=n-(k+1)+r=n-k+(r-1)=2$$.

Thus in either case, $$n-m+r=2$$ as desired. Q.E.D.

## References

John M. Harris, J. L. H., & Mossinghoff, M. J. (2000). *Combinatorics and Graph Theory*. Springer.