Euler's formula for Planar Graph

June 24, 2010

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^{\prime }=(V,E\setminus e)$ of G. $G^{\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^{\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^{\prime }$ is a connected planar graph with $|E\setminus e|=k$ edges. Thus the inductive hypothesis applies to $G^{\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 #

% reference combinatorics_and_graph_theory -l 37 %

• Graph Theory,
• Proof,
• Mathematics,
• Combinatorics