Skip to main content
\(\newcommand{\set}[1]{\{1,2,\dotsc,#1\,\}} \newcommand{\ints}{\mathbb{Z}} \newcommand{\posints}{\mathbb{N}} \newcommand{\rats}{\mathbb{Q}} \newcommand{\reals}{\mathbb{R}} \newcommand{\complexes}{\mathbb{C}} \newcommand{\twospace}{\mathbb{R}^2} \newcommand{\threepace}{\mathbb{R}^3} \newcommand{\dspace}{\mathbb{R}^d} \newcommand{\nni}{\mathbb{N}_0} \newcommand{\nonnegints}{\mathbb{N}_0} \newcommand{\dom}{\operatorname{dom}} \newcommand{\ran}{\operatorname{ran}} \newcommand{\prob}{\operatorname{prob}} \newcommand{\Prob}{\operatorname{Prob}} \newcommand{\height}{\operatorname{height}} \newcommand{\width}{\operatorname{width}} \newcommand{\length}{\operatorname{length}} \newcommand{\crit}{\operatorname{crit}} \newcommand{\inc}{\operatorname{inc}} \newcommand{\HP}{\mathbf{H_P}} \newcommand{\HCP}{\mathbf{H^c_P}} \newcommand{\GP}{\mathbf{G_P}} \newcommand{\GQ}{\mathbf{G_Q}} \newcommand{\AG}{\mathbf{A_G}} \newcommand{\GCP}{\mathbf{G^c_P}} \newcommand{\PXP}{\mathbf{P}=(X,P)} \newcommand{\QYQ}{\mathbf{Q}=(Y,Q)} \newcommand{\GVE}{\mathbf{G}=(V,E)} \newcommand{\HWF}{\mathbf{H}=(W,F)} \newcommand{\bfC}{\mathbf{C}} \newcommand{\bfG}{\mathbf{G}} \newcommand{\bfH}{\mathbf{H}} \newcommand{\bfF}{\mathbf{F}} \newcommand{\bfI}{\mathbf{I}} \newcommand{\bfK}{\mathbf{K}} \newcommand{\bfP}{\mathbf{P}} \newcommand{\bfQ}{\mathbf{Q}} \newcommand{\bfR}{\mathbf{R}} \newcommand{\bfS}{\mathbf{S}} \newcommand{\bfT}{\mathbf{T}} \newcommand{\bfNP}{\mathbf{NP}} \newcommand{\bftwo}{\mathbf{2}} \newcommand{\cgA}{\mathcal{A}} \newcommand{\cgB}{\mathcal{B}} \newcommand{\cgC}{\mathcal{C}} \newcommand{\cgD}{\mathcal{D}} \newcommand{\cgE}{\mathcal{E}} \newcommand{\cgF}{\mathcal{F}} \newcommand{\cgG}{\mathcal{G}} \newcommand{\cgM}{\mathcal{M}} \newcommand{\cgN}{\mathcal{N}} \newcommand{\cgP}{\mathcal{P}} \newcommand{\cgR}{\mathcal{R}} \newcommand{\cgS}{\mathcal{S}} \newcommand{\bfn}{\mathbf{n}} \newcommand{\bfm}{\mathbf{m}} \newcommand{\bfk}{\mathbf{k}} \newcommand{\bfs}{\mathbf{s}} \newcommand{\bijection}{\xrightarrow[\text{onto}]{\text{$1$--$1$}}} \newcommand{\injection}{\xrightarrow[]{\text{$1$--$1$}}} \newcommand{\surjection}{\xrightarrow[\text{onto}]{}} \newcommand{\nin}{\not\in} \newcommand{\prufer}{\mbox{prüfer}} \DeclareMathOperator{\fix}{fix} \DeclareMathOperator{\stab}{stab} \DeclareMathOperator{\var}{var} \newcommand{\inv}{^{-1}} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \)

Section4.5Euler's Theorem

This section cover's Euler's theorem on planar graphs and its applications. We give a proof by of Euler's theorem by induction, and gave several applications of the theorem itself: more proofs that \(K_{3,3}\) and \(K_5\) aren't planar, that footballs have five pentagons, and a proof that our video game designers couldn't have made their map into a sphere without doing something very strange.

Subsection4.5.1counting Faces

A face of a planar drawing of a graph is a region bounded by edges and vertices and not containing any other vertices or edges.

Figure 4.5.1 shows a planar drawing of a graph with \(6\) vertices and \(9\) edges. Notice how one of the edges is drawn as a true polygonal arc rather than a straight line segment. This drawing determines \(5\) regions, since we also count the unbounded region that surrounds the drawing.

Figure4.5.1A planar drawing of a graph

Figure 4.5.2 shows a planar drawing of the complete graph \(\bfK_4\text{.}\) There are \(4\) vertices, \(6\) edges, and \(4\) faces in the drawing.

Figure4.5.2A planar drawing of \(\bfK_4\)

What happens if we compute the number of vertices minus the number of edges plus the number of faces for these drawings? We have

\begin{align*} 6-9+5 \amp = 2\\ 4-6+4 \amp =2 \end{align*}

While it might seem like a coincidence that this computation results in \(2\) for these planar drawings, there's a more general principle at work here, and in fact it holds for any planar drawing of any planar graph.

In fact, the number \(2\) here actually results from a fundamental property of the plane, and there are a corresponding theorems for other surfaces. However, we only need the result as stated above.

Our proof is by induction on the number \(m\) of edges. If \(m=0\text{,}\) then since \(\bfG\) is connected, our graph has a single vertex, and so there is one face. Thus \(n-m+f = 1-0+1=2\) as needed. Now suppose that we have proven Euler's formula for all graphs with less than \(m\) edges and let \(\bfG\) have \(m\) edges. Pick an edge \(e\) of \(\bfG\text{.}\) What happens if we form a new graph \(\bfG'\) by deleting \(e\) from \(\bfG\text{?}\) If \(\bfG'\) is connected, our inductive hypothesis applies. Say that \(\bfG'\) has \(n'\) vertices, \(m'\) edges, and \(f'\) faces. Then by induction, these numbers satisfy

\begin{equation*} n'-m'+f'=2. \end{equation*}

Since we only deleted one edge, \(n'=n\) and \(m'=m-1\text{.}\) What did the removal of \(e\) do to the number of faces? In \(\bfG'\) there's a new face that was formerly two faces divided by \(e\) in \(\bfG\text{.}\) Thus, \(f'=f-1\text{.}\) Substituting these into \(n'-m'+f'=2\text{,}\) we have

\begin{equation*} n-(m-1)+(f-1)=2 \iff n-m+f=2. \end{equation*}

Thus, if \(\bfG'\) is connected, we are done. If \(\bfG'\) is disconnected, however, we cannot apply the inductive assumption to \(\bfG'\) directly. Fortunately, since we removed only one edge, \(\bfG'\) has two components, which we can view as two connected graphs \(\bfG'_1\) and \(\bfG'_2\text{.}\) Each of these has fewer than \(m\) edges, so we may apply the inductive hypothesis to them. For \(i=1,2\text{,}\) let \(n'_i\) be the number of vertices of \(\bfG'_i\text{,}\) \(m'_i\) the number of edges of \(\bfG'_i\text{,}\) and \(f'_i\) the number of faces of \(\bfG'_i\text{.}\) Then by induction we have

\begin{equation*} n'_1 - m'_1 + f'_1 = 2 \quad \text{and} \quad n'_2-m'_2+f'_2 =2. \end{equation*}

Adding these together, we have

\begin{equation*} (n'_1 + n'_2) - (m'_1 + m'_2) + (f'_1 + f'_2) = 4. \end{equation*}

But now \(n=n'_1 + n'_2\text{,}\) and \(m'_1 + m'_2 = m-1\text{,}\) so the equality becomes

\begin{equation*} n - (m-1) + (f'_1+f'_2) = 4 \iff n-m + (f'_1 + f'_2) = 3. \end{equation*}

The only thing we have yet to figure out is how \(f'_1+f'_2\) relates to \(f\text{,}\) and we have to hope that it will allow us to knock the \(3\) down to a \(2\text{.}\) Every face of \(\bfG'_1\) and \(\bfG'_2\) is a face of \(\bfG\text{,}\) since the fact that removing \(e\) disconnects \(\bfG\) means that \(e\) must be part of the boundary of the unbounded face. Further, the unbounded face is counted twice in the sum \(f'_1 + f'_2\text{,}\) so \(f=f'_1 + f'_2 -1\text{.}\) This gives exactly what we need to complete the proof.

Remark4.5.4Alternative method of dealing with the second case

In our proof of Euler's theorem, the most complicated part was dealing with the situation if the edge \(e\) disconnects our graph \(\bfG\) when we remove it. In this case, instead of deleting the edge \(e\) we can contract it -- that is, shrink it to a point. This would have result in a graph that is still planar and still connected, but with one less edge (\(e\) is no longer around), and one less vertex (the two vertices \(e\) connects are now merged into one). The number of faces remains unchanged. So the number of edges and the number of faces each decreased by one, these two changes cancel out when we calculate \(n-m+f\text{,}\) and hence both are equal to two.

Subsection4.5.2Applications of Euler's theorem

By itself, Euler's theorem doesn't seem that useful: there are three variables (the numbers of edges, vertices, and faces) and only one equation between them, so there are still lots of degrees of freedom. For it to be particularly useful, we want to have other relationships between these numbers. In many applications, these relationships can come from handshaking.

Recall that Euler's handshaking lemma said that

\begin{equation*} \sum_{v\in G} d(v)=2 |E(G), \end{equation*}

the sum of the degrees of all the vertices is twice the number of edges. If we had some knowledge about the degrees of these vertices, we could get another relationship between the number of vertices and the number of edges. For example, if \(G\) is regular of degree \(k\text{,}\) then every vertex has degree \(k\text{,}\) and hence the sum of all the degrees is just \(kn\text{.}\) Hence, handshaking would tell us that \(kn=2m\text{,}\) and we would have another relationship between the three variables \(m,n\) and \(f\text{.}\)

Similarly, there is a handshaking between faces and edges. Let the degree of a face be the number of edges that occur around it -- so, a triangle would have degree three. Then, if we sum up the degrees of all the faces, we're counting each edge twice again -- once from the face on its left, and once from the face on its right. so we have

\begin{equation*} sum_{f\in \text{faces}(G)}d(f)=2 |E(G)| \end{equation*}

Note that this is just the usual vertex-edge handshaking for the dual graph.

Thus, vertex-edge and face-edge handshaking can potentially give us two other sources of relationships between the numbers of vertices, edges, and faces. Most applications of Euler's theorem proceed by combining all three relationships, as we shall see.