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 nm+r=2.

Proof by induction


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 nm+r=10+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 mk, edges, and r regions, nm+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=n1 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 nm+r=n(n1)+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=(V,E{e}) of G. G must be connected because removing an edge from a cycle breaks the cycle but does not break the connectivity of the graph. Furthermore, G 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 is a connected planar graph with |E{e}|=k edges. Thus the inductive hypothesis applies to G and yields nk+(r1)=2. Therefore, nm+r=n(k+1)+r=nk+(r1)=2.

Thus in either case, nm+r=2 as desired. Q.E.D.


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