🔗 4.

3 Planar Graphs
🔗 Investigate!
When a connected graph can be drawn without any edges crossing, it is
called planar. When a planar graph is drawn in this way, it divides the plane
into regions called faces.
1. Draw, if possible, two different planar graphs with the same number of
vertices, edges, and faces.
2. Draw, if possible, two different planar graphs with the same number of
vertices and edges, but a different number of faces.

🔗 When is it possible to draw a graph so that none of the edges cross? If this is
possible, we say the graph is planar (since you can draw it on the plane).

🔗 Notice that the definition of planar includes the phrase “it is possible to.” This
means that even if a graph does not look like it is planar, it still might be.
Perhaps you can redraw it in a way in which no edges cross. For example, this is
a planar graph:

🔗 That is because we can redraw it like this:

🔗 The graphs are the same, so if one is planar, the other must be too. However,
the original drawing of the graph was not a planar representation of the graph.

🔗 When a planar graph is drawn without edges crossing, the edges and vertices of
the graph divide the plane into regions. We will call each region a face. The
graph above has 3 faces (yes, we do include the “outside” region as a face). The
number of faces does not change no matter how you draw the graph (as long as
you do so without the edges crossing), so it makes sense to ascribe the number
of faces as a property of the planar graph.

🔗 WARNING: you can only count faces when the graph is drawn in a planar way.
For example, consider these two representations of the same graph:
🔗 If you try to count faces using the graph on the left, you might say there are 5
faces (including the outside). But drawing the graph with a planar representation
shows that in fact there are only 4 faces.

🔗 There is a connection between the number of vertices ( ), the number of edges (

v

e ) and the number of faces (f ) in any connected planar graph. This relationship
is called Euler’s formula.

🔗
Euler’s Formula for Planar Graphs.
🔗 For any connected planar graph with v vertices, e edges and f faces, we
have

v − e + f = 2 .

🔗 Why is Euler’s formula true? One way to convince yourself of its validity is to
draw a planar graph step by step. Start with the graph P :2

🔗 Any connected graph (besides just a single isolated vertex) must contain this
subgraph. Now build up to your graph by adding edges and vertices. Each step
will consist of either adding a new vertex connected by a new edge to part of
your graph (so creating a new “spike”) or by connecting two vertices already in
the graph with a new edge (completing a circuit).

🔗 What do these “moves” do? When adding the spike, the number of edges
increases by 1, the number of vertices increases by one, and the number of
faces remains the same. But this means that v − e + f does not change.
 Completing a circuit adds one edge, adds one face, and keeps the number of
vertices the same. So again, v − e + f does not change.

🔗 Since we can build any graph using a combination of these two moves, and
doing so never changes the quantity v − e + f , that quantity will be the same
for all graphs. But notice that our starting graph P has v = 2, e = 1 and f = 1,
2

so v − e + f = 2. This argument is essentially a proof by induction. A good

exercise would be to rewrite it as a formal induction proof.

🔗 Non-planar Graphs
Investigate!
🔗 For the complete graphs , we would like to be able to say something
Kn

about the number of vertices, edges, and (if the graph is planar) faces. Let’s
first consider K : 3

1. How many vertices does K have? How many edges?

3

2. If K is planar, how many faces should it have?

3

🔗 Repeat parts (1) and (2) for , , and .

K4 K5 K23

🔗 What about complete bipartite graphs? How many vertices, edges, and faces
(if it were planar) does K 7,4 have? For which values of m and n are K and
n

K m,n planar?

🔗 Not all graphs are planar. If there are too many edges and too few vertices, then
some of the edges will need to intersect. The smallest graph where this happens
is K .
5

🔗 If you try to redraw this without edges crossing, you quickly get into trouble.
There seems to be one edge too many. In fact, we can prove that no matter how
you draw it, K will always have edges crossing.
5

🔗
Theorem 4.3.1.
🔗 is not planar.
K5

🔗 Proof. The proof is by contradiction. So assume that K5 is planar. Then the

graph must satisfy Euler’s formula for planar graphs. K 5 has 5 vertices and
 10 edges, so we get

5 − 10 + f = 2 ,

🔗 which says that if the graph is drawn without any edges crossing, there
would be f = 7 faces.

🔗 Now consider how many edges surround each face. Each face must be
surrounded by at least 3 edges. Let B be the total number of boundaries
around all the faces in the graph. Thus we have that 3f ≤ B. But also
B = 2e, since each edge is used as a boundary exactly twice. Putting this

together we get

.
3f ≤ 2e

🔗 But this is impossible, since we have already determined that f = 7 and

e = 10 , and 21 ≰ 20. This is a contradiction so in fact K 5 is not planar.

🔗 The other simplest graph which is not planar is K3,3

🔗 Proving that is not planar answers the houses and utilities puzzle: it is not
K3,3

possible to connect each of three houses to each of three utilities without the
lines crossing.

🔗
Theorem 4.3.2.
🔗 is not planar.
K3,3

🔗 Proof. Again, we proceed by contradiction. Suppose were planar.

K3,3

Then by Euler’s formula there will be 5 faces, since v = 6, e = 9, and

6 − 9 + f = 2.

🔗 How many boundaries surround these 5 faces? Let be this number. Since
B

each edge is used as a boundary twice, we have B = 2e. Also, B ≥ 4f since

each face is surrounded by 4 or more boundaries. We know this is true
because K is bipartite, so does not contain any 3-edge cycles. Thus
3,3

.
4f ≤ 2e

🔗 But this would say that , which is clearly false. Thus K

20 ≤ 18 3,3 is not
planar.
🔗 Note the similarities and differences in these proofs. Both are proofs by
contradiction, and both start with using Euler’s formula to derive the (supposed)
number of faces in the graph. Then we find a relationship between the number
of faces and the number of edges based on how many edges surround each
face. This is the only difference. In the proof for K , we got 3f ≤ 2e and for K
5 3,3

we go 4f ≤ 2e. The coefficient of f is the key. It is the smallest number of edges

which could surround any face. If some number of edges surround a face, then
these edges form a cycle. So that number is the size of the smallest cycle in the
graph.

🔗 In general, if we let be the size of the smallest cycle in a graph (g stands for
g

girth, which is the technical term for this) then for any planar graph we have
gf ≤ 2e. When this disagrees with Euler’s formula, we know for sure that the

graph cannot be planar.

🔗 Polyhedra
Investigate!
🔗 A cube is an example of a convex polyhedron. It contains 6 identical squares
for its faces, 8 vertices, and 12 edges. The cube is a regular polyhedron (also
known as a Platonic solid) because each face is an identical regular polygon
and each vertex joins an equal number of faces.

🔗 There are exactly four other regular polyhedra: the tetrahedron, octahedron,
dodecahedron, and icosahedron with 4, 8, 12 and 20 faces respectively. How
many vertices and edges do each of these have?

🔗 Another area of mathematics where you might have heard the terms “vertex,”
“edge,” and “face” is geometry. A polyhedron is a geometric solid made up of flat
polygonal faces joined at edges and vertices. We are especially interested in
convex polyhedra, which means that any line segment connecting two points on
the interior of the polyhedron must be entirely contained inside the polyhedron.
7

🔗 Notice that since 8 − 12 + 6 = 2, the vertices, edges and faces of a cube satisfy
Euler’s formula for planar graphs. This is not a coincidence. We can represent a
cube as a planar graph by projecting the vertices and edges onto the plane. One
such projection looks like this:

🔗 In fact, every convex polyhedron can be projected onto the plane without edges
crossing. Think of placing the polyhedron inside a sphere, with a light at the
 center of the sphere. The edges and vertices of the polyhedron cast a shadow
onto the interior of the sphere. You can then cut a hole in the sphere in the
middle of one of the projected faces and “stretch” the sphere to lie down flat on
the plane. The face that was punctured becomes the “outside” face of the planar
graph.

🔗 The point is, we can apply what we know about graphs (in particular planar
graphs) to convex polyhedra. Since every convex polyhedron can be
represented as a planar graph, we see that Euler’s formula for planar graphs
holds for all convex polyhedra as well. We also can apply the same sort of
reasoning we use for graphs in other contexts to convex polyhedra. For
example, we know that there is no convex polyhedron with 11 vertices all of
degree 3, as this would make 33/2 edges.

🔗 Example 4.3.3.
🔗 Is there a convex polyhedron consisting of three triangles and six pentagons?
What about three triangles, six pentagons and five heptagons (7-sided
polygons)?
Solution.

How many edges would such polyhedra have? For the first proposed
polyhedron, the triangles would contribute a total of 9 edges, and the
pentagons would contribute 30. However, this counts each edge twice
(as each edge borders exactly two faces), giving 39/2 edges, an
impossibility. There is no such polyhedron.

The second polyhedron does not have this obstacle. The extra 35 edges
contributed by the heptagons give a total of 74/2 = 37 edges. So far so
good. Now how many vertices does this supposed polyhedron have? We
can use Euler’s formula. There are 14 faces, so we have v − 37 + 14 = 2
or equivalently v = 25. But now use the vertices to count the edges
again. Each vertex must have degree at least three (that is, each vertex
joins at least three faces since the interior angle of all the polygons must
be less that 180 ), so the sum of the degrees of vertices is at least 75.
∘

Since the sum of the degrees must be exactly twice the number of
edges, this says that there are strictly more than 37 edges. Again, there
is no such polyhedron.

🔗 To conclude this application of planar graphs, consider the regular polyhedra.

We claimed there are only five. How do we know this is true? We can prove it
using graph theory.

🔗
Theorem 4.3.4.
🔗 There are exactly five regular polyhedra.
🔗 Proof. Recall that all the faces of a regular polyhedron are identical regular
polygons, and that each vertex has the same degree. Consider four cases,
depending on the type of regular polygon.

🔗 Case 1: Each face is a triangle. Let be the number of faces. There are then
f

3f /2 edges. Using Euler’s formula we have v − 3f /2 + f = 2 so

v = 2 + f /2. Now each vertex has the same degree, say k. So the number

of edges is also kv/2. Putting this together gives

3f k(2 + f /2)
e = = ,
2 2

🔗 which says
6f
k = .
4 + f

🔗 Both k and f must be positive integers. Note that is an increasing

4+f
6f

function for positive f , bounded above by a horizontal asymptote at k = 6.

Thus the only possible values for k are 3, 4, and 5. Each of these are
possible. To get k = 3, we need f = 4 (this is the tetrahedron). For k = 4
we take f = 8 (the octahedron). For k = 5 take f = 20 (the icosahedron).
Thus there are exactly three regular polyhedra with triangles for faces.

🔗 Case 2: Each face is a square. Now we have . Using Euler’s

e = 4f /2 = 2f

formula we get v = 2 + f , and counting edges using the degree k of each

vertex gives us
k(2 + f )
e = 2f = .
2

🔗 Solving for k gives

4f 8f
k = = .
2 + f 4 + 2f

🔗 This is again an increasing function, but this time the horizontal asymptote
is at k = 4, so the only possible value that k could take is 3. This produces 6
faces, and we have a cube. There is only one regular polyhedron with
square faces.

🔗 Case 3: Each face is a pentagon. We perform the same calculation as above,

this time getting e = 5f /2 so v = 2 + 3f /2. Then

5f k(2 + 3f /2)
e = = ,
2 2

🔗 so
 10f
k = .
4 + 3f

🔗 Now the horizontal asymptote is at . This is less than 4, so we can only

10

hope of making k = 3. We can do so by using 12 pentagons, getting the

dodecahedron. This is the only regular polyhedron with pentagons as faces.

🔗 Case 4: Each face is an -gon with n ≥ 6. Following the same procedure as

n

above, we deduce that

2nf
k = ,
4 + (n − 2)f

🔗 which will be increasing to a horizontal asymptote of . When n = 6, this

2n

n−2

asymptote is at k = 3. Any larger value of n will give an even smaller

asymptote. Therefore no regular polyhedra exist with faces larger than
pentagons. 8

🔗 Exercises
🔗 1. Is it possible for a planar graph to have 6 vertices, 10 edges and 5 faces?
Explain.
Solution.

No. A (connected) planar graph must satisfy Euler’s formula:

v − e + f = 2. Here v − e + f = 6 − 10 + 5 = 1.

🔗 2. The graph Ghas 6 vertices with degrees 2, 2, 3, 4, 4, 5. How many edges

does G have? Could G be planar? If so, how many faces would it have. If not,
explain.
Solution.

G has 10 edges, since 10 = 2+2+3+4+4+5

2
. It could be planar, and then it
would have 6 faces, using Euler’s formula: 6 − 10 + f = 2 means f = 6.
To make sure that it is actually planar though, we would need to draw a
graph with those vertex degrees without edges crossing. This can be done
by trial and error (and is possible).

🔗 3. Is it possible for a connected graph with 7 vertices and 10 edges to be drawn

so that no edges cross and create 4 faces? Explain.
Hint.

What would Euler’s formula tell you?

🔗 4. Is it possible for a graph with 10 vertices and edges to be a connected planar
graph? Explain.

🔗 5. Is there a connected planar graph with an odd number of faces where every
vertex has degree 6? Prove your answer.
Hint.

You can use the handshake lemma to find the number of edges, in terms
of v, the number of vertices.

🔗 6. I’m thinking of a polyhedron containing 12 faces. Seven are triangles and four
are quadralaterals. The polyhedron has 11 vertices including those around the
mystery face. How many sides does the last face have?
Solution.

Say the last polyhedron has n edges, and also n vertices. The total number
of edges the polyhedron has then is (7 ⋅ 3 + 4 ⋅ 4 + n)/2 = (37 + n)/2.
In particular, we know the last face must have an odd number of edges.
We also have that v = 11. By Euler’s formula, we have
11 − (37 + n)/2 + 12 = 2, and solving for n we get n = 5, so the last

face is a pentagon.

🔗 7. Consider some classic polyhedrons.

(a) An octahedron is a regular polyhedron made up of 8 equilateral triangles
(it sort of looks like two pyramids with their bases glued together). Draw a
planar graph representation of an octahedron. How many vertices, edges
and faces does an octahedron (and your graph) have?
(b) The traditional design of a soccer ball is in fact a (spherical projection of a)
truncated icosahedron. This consists of 12 regular pentagons and 20
regular hexagons. No two pentagons are adjacent (so the edges of each
pentagon are shared only by hexagons). How many vertices, edges, and
faces does a truncated icosahedron have? Explain how you arrived at your
answers. Bonus: draw the planar graph representation of the truncated
icosahedron.
(c) Your “friend” claims that he has constructed a convex polyhedron out of 2
triangles, 2 squares, 6 pentagons and 5 octagons. Prove that your friend is
lying. Hint: each vertex of a convex polyhedron must border at least three
faces.

🔗 8. Prove Euler’s formula using induction on the number of edges in the graph.
Solution.
 Proof. Let P (n) be the statement, “every connected planar graph
containing n edges satisfies v − n + f = 2.” We will show P (n) is
true for all n ≥ 0.

Base case: there is only one graph with zero edges, namely a single
isolated vertex. In this case v = 1, f = 1 and e = 0, so Euler’s
formula holds.

Inductive case: Suppose P (k) is true for some arbitrary k ≥ 0. Now

consider an arbitrary graph containing k + 1 edges (and v vertices
and f faces). No matter what this graph looks like, we can remove a
single edge to get a graph with k edges which we can apply the
inductive hypothesis to.

There are two cases: either the graph contains a cycle or it does not. If
the graph contains a cycle, then pick an edge that is part of this cycle,
and remove it. This will not disconnect the graph, and will decrease
the number of faces by 1 (since the edge was bordering two distinct
faces). So by the inductive hypothesis we will have v − k + f − 1 = 2.
Adding the edge back will give v − (k + 1) + f = 2 as needed.

If the graph does not contain a cycle, then it is a tree, so has a vertex
of degree 1. Then we can pick the edge to remove to be incident to
such a degree 1 vertex. In this case, also remove that vertex. The
smaller graph will now satisfy v − 1 − k + f = 2 by the induction
hypothesis (removing the edge and vertex did not reduce the number
of faces). Adding the edge and vertex back gives v − (k + 1) + f = 2,
as required.

Therefore, by the principle of mathematical induction, Euler’s formula

holds for all planar graphs.

🔗 9. Prove Euler’s formula using induction on the number of vertices in the graph.
🔗 10. Euler’s formula ( v − e + f = 2) holds for all connected planar graphs. What
if a graph is not connected? Suppose a planar graph has two components. What
is the value of v − e + f now? What if it has k components?

🔗 11. Prove that the Petersen graph (below) is not planar.