SECTION 2.2 Elementary Graph Theory 141
From which it follows that e′ ≤ 3 v′− 6. However, e′ = e−k and
v′=v−k for some fixed non-negative integer k from which we infer
that e≤ 3 v−6.
Example 4. From the above result, we see immediately that the
complete graph K 5 is not planar as it has
Ä 5
2ä
= 10 edges which is
greater than 3v−6 = 9.
If we have a planar bipartite graph, then the above result can be
strengthened:
Corollary. LetM be a simple planar map with no triangles. Then
we have e≤ 2 v− 4.
Proof. As in the above proof, that each edge bounds two faces and
that each face—including the infinite face—will be bounded by at least
four edges (there are no triangles). This implies that 4f ≤ 2 e. There-
fore,
2 = v−e+f ≤v−e+e/2 =v−e/ 2 ,and soe≤ 2 v−4 in this case.
Example 5. From the above result, we see immediately that the
complete bipartite graphK 3 , 3 is not planar. Being bipartite, it cannot
have any triangles (see Exercise 5), furthermore, it has 9 edges which
is greater than 2v−4 = 8.
Exercises
- Show that even though the degree of each vertex in both graphs
below is 3, these graphs arenotisomorphic.