Skip to main content

Section 4.5 Euler's Theorem

This section cover's Euler's theorem on planar graphs and its applications. After defining faces, we state 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.

Subsection 4.5.1 Counting 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 two graphs. The left graph has determines \(5\) regions, since we also count the unbounded region that surrounds the drawing.

Figure 4.5.1. Two planar graphs

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.

Remark 4.5.3. Alternative 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.

Subsection 4.5.2 Applications 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.

We give a proof by contradiction. Suppose \(K_5\) was planar, and draw it on the plane. We know that \(K_5\) has 5 vertices and \(\binom{5}{2}=10\) edges, and so by Euler theorem we know that any drawing of it must have 7 faces. We now use edge-face handshaking to get a contradiction.

What could the degrees of the faces be? We don't know for sure, but we know that none of the faces could have degree one or two, as then the edges would form a loop or multiple edges between two vertices, but \(K_5\) is simple. Hence, every face must have \(d(f)\geq 3\text{.}\) But then handshaking gives:

\begin{equation*} 20=2e=\sum d(f)\geq \sum 3=3\cdot 7=21 \end{equation*}

which is the desired contradiction, and so we conclude that \(K_5\) is not, in fact, planar.

It is a good exercise to adapt this proof to prove that \(K_{3,3}\) isn't planar; one needs to use the extra fact that \(K_{3,3}\) doesn't have any three cycles (why not?)

We now prove that footballs have 12 pentagons. More precisely, use the shorthand football graph to mean any trivalent graph drawn on the plane so that every face is a pentagon or hexagon. Then we have:

Let \(V, E, F\) denote the number of vertices, edges, and faces of \(\bfG\text{.}\) Since every face is a hexagon or pentagon, we have \(E=P+H\text{,}\) and substituting this into Euler's theorem gives:

\begin{equation} V-E+P+H=2\label{footeu}\tag{4.5.1} \end{equation}

Now we turn handshaking. Since \(\bfG\) is trivalent, every vertex has degree three, and so vertex-edge handshaking becomes:

\begin{equation} 2E=3V\label{footve}\tag{4.5.2} \end{equation}

Finally, since there are \(P\) pentagonal faces and \(H\) hexagonal faces, face-edge handshaking becomes:

\begin{equation} 2E=5P+6H\label{footfe}\tag{4.5.3} \end{equation}

Multiplying (4.5.1) by six gives:

\begin{equation*} 6V-6E+6P+6H=12 \end{equation*}

Multiplying (4.5.2) by two gives \(6V-4E=0\text{,}\) which we can use to eliminate \(V\text{,}\) giving

\begin{equation*} -2E+5P+6H=12 \end{equation*}

Finally, using (4.5.3) we can eliminate both \(E\) and \(H\) in one go, being left with \(P=12\) as desired.

Finally, we prove that given some sensible restraints, video game designers cannot make a world map that's a sphere. A videogame world locally looks like a square grid -- with every vertex and face having degree four.

Since every vertex has degree 4, vertex-edge handshaking gives \(2E=4V\text{,}\) and since every face has degree 4, face-edge handshaking gives \(2E=4F\text{.}\) Thus, we see \(V=F=E/2\text{,}\) and plugging this in gives:

\begin{equation*} V-E+F=E/2-E+E/2=0 \end{equation*}

which contradicts Euler's Theorem. Hence, such a graph on a sphere is not possible.