138 CHAPTER 2 Discrete Mathematics
The next planarity condition is somewhat more useful but slightly
more technical. First of all, a graphH is called aminorof the graph
GifH is isomorphic to a graph that can be obtained by a number of
edge contractions on a subgraph ofG. Look at the so-calledPetersen
graph; it containsK 5 as a minor:
Theorem. (Wagner’s Theorem)A finite graphGis planar if and only
if it does not haveK 5 orK 3 , 3 as a minor.
As a result, we see that the Petersen graph is not planar.