SECTION 2.2 Elementary Graph Theory 137
There are two fundamental theorems which give criteria for a graph
to be planar. They’re relatively deep results, so we won’t give proofs
here. The first result makes use of the notion of “homeomorphism” of
graphs. Namely, two graphs arehomeomorphicif one can be obtained
from the other simply by adding vertices along existing edges. However,
no new edges can be added!
Theorem. (Kuratowski’s Theorem)A finite graphGis planar if and
only if G has no subgraph homeomorphic to the complete graphK 5
on five vertices or the complete bipartite graphK 3 , 3.
From Kuratowski’s theorem we can deduce that the Petersen graph is
not planar. Indeed, the sequence below shows that the Petersen graph
has a subgraph which is homeomorphic with the complete bipartite
graphK 3 , 3.