Theorem 5.2. Euler’s Formula.
Let \(\bfG\) be a connected planar graph with \(n\) vertices and \(m\) edges. Then every planar drawing of \(\bfG\) has \(f\) faces, where \(f\) satisfies \(n-m+f=2\text{.}\)
Print preview
Worksheet 5.3 Euler’s Polyhedral Formula
It turns out that you could draw hundreds of connected planar graphs and keep finding the same pattern that arises in the platonic solids:
1.
Notice that Euler’s Formula requires that \(\bfG\) be a connected planar graph. Find a counterexample to show that the formula \(n-m+f=2\) does not hold if \(\bfG\) is a planar graph that is not connected.
2.
Since \(\bfG\) must be connected, we start by considering the minimal case in which \(\bfG\) has no cycles (but for the general number \(n\) of vertices). What type of graph does that mean \(\bfG\) is? How many edges does \(\bfG\) have (in terms of \(n\))? (In future questions, I’ll call this value of \(m\) by the name \(m_{0}\text{.}\)) Verify Euler’s formula in this case.
3.
(a)
Draw a planar drawing of a connected planar graph \(\bfG\) with with \(n=7\) or \(n=8\) vertices and more than \(m_{0}\) edges. Make sure your graph has at least one vertex of degree \(1\text{.}\)
(b)
(c)
Is there an edge \(e\) you can erase from your graph and leave a graph \(\bfG'\) that is still connected? What determines whether or not an edge is safe to remove while still leaving a connected graph?
(d)
Erase an edge \(e\) from \(\bfG\) to give you a planar drawing of a connected planar graph \(\bfG'\text{.}\) Let \(n'\text{,}\) \(m'\text{,}\) and \(f'\) be the number of vertices, edges, and faces respectively of \(\bfG'\text{.}\) What are \(n',m',f'\) for your graph?
(e)
Find equations that relate \(n'\text{,}\) \(m'\text{,}\) and \(f'\) to \(n\text{,}\) \(m\text{,}\) and \(f\text{.}\)
4.
Now let’s suppose that \(\bfG\) is a connected planar graph with \(n\) vertices and \(m\) edges where \(m\gt m_{0}\text{.}\) Suppose that Euler’s formula holds for any connected planar graph with fewer than \(m\) edges. (What type of proof are we setting up here?)
(a)
Why is there an edge \(e\) you can delete from \(\bfG\) to produce a connected planar graph \(\bfG'\text{?}\)
(b)
Let \(n'\text{,}\) \(m'\text{,}\) and \(f'\) be the number of vertices, edges, and faces respectively of \(\bfG'\text{.}\) What are \(n',m',f'\) in terms of \(n\text{,}\) \(m\text{,}\) and \(f\text{?}\)
(c)
(d)
Prove that \(n-m+f=2\text{.}\)
5.
In the grand scheme of things, Euler’s formula doesn’t seem that useful for determining if a graph is planar or not. However, we can deduce something useful from it. In this problem, we’re going to imagine a fixed planar drawing of a connected planar graph \(\bfG\) and let \(n\text{,}\) \(m\text{,}\) and \(f\) be the number of vertices, edges, and faces, respectively, in our planar drawing. We’ll assume that \(n\geq 4\) to avoid some annoying things.
Let \(S = \set{(e,F)\mid e\text{ is an edge of }\bfG\text{ and part of the boundary of face }F}\text{.}\)
(a)
If I pick an edge \(e_{1}\) of \(\bfG\text{,}\) what is the largest possible number of faces that \(e_{1}\) can be part of the boundary of? So what does that tell us about the number of ordered pairs in \(S\) that have \(e_{1}\) as the first coordinate?
(b)
(c)
If I pick a face \(F_{1}\) of \(\bfG\text{,}\) what is the smallest possible number of edges that can be used to form the boundary of \(F_{1}\text{?}\)
(d)
(e)
(f)
Using Euler’s formula and the previous part, show that \(m\leq 3n-6\text{.}\)
(g)
Prove that \(\bfK_{5}\) is not planar.
6.
Recall that the complete bipartite graph \(\bfK_{3,3}\) is the bipartite graph with two independent sets each of size three and all the possible edges (nine in total) between vertices in different independent sets.
(a)
Can you make a planar drawing of \(\bfK_{3,3}\text{?}\) If not, what does the \(m\leq 3n-6\) restriction tell you here?
(b)
Notice that since \(\bfK_{3,3}\) does not contain any vertices of degree \(1\text{,}\) every face of a planar drawing would be bounded by a cycle, and thus every edge is part of the boundary of two faces. Since \(\bfK_{3,3}\) is bipartite, what can you say about the length of every cycle in \(\bfK_{3,3}\text{?}\)
(c)
As in the previous problem, count edge-face pairs. How many pairs must there be for \(\bfK_{3,3}\text{?}\)
(d)
Let \(f_{4}\) be the number of faces bounded by a cycle of length \(4\) and let \(f_{6}\) be the number of faces bounded by a cycle of length \(6\text{.}\) Express the total number of faces \(f\) in terms of \(f_{4}\) and \(f_{6}\text{.}\) Then express the number of edge-face pairs in terms of \(f_{4}\) and \(f_{6}\text{.}\)
(e)
What does Euler’s formula tell you \(f\) would have to be for \(\bfK_{3,3}\text{?}\) What lower bound does this give you for the number of edge-face pairs, and how does this show that \(\bfK_{3,3}\) is not planar?
7.
For each graph on the next page, find a planar drawing or give a reason why the graph is not planar.
