Section 6.1 Graphs and Their Representations
491
A graph that is planar cannot be turned into a nonplanar graph by elementary
subdivisions, and a graph that is nonplanar cannot be turned into a planar graph
by elementary subdivisions (see Exercise 32). As a result, homeomorphic graphs
are either both planar or both nonplanar. The following theorem, due to the Polish
mathematician Kazimierz Kuratowski, characterizes nonplanar graphs.
example 14
K 5 is a simple, connected graph with 5 nodes (and 10 arcs). If it were a planar graph,
inequality (2) of our theorem would hold, but 10 > 3(5) − 6. Therefore, just as our
construction argument showed, K 5 is not planar. K 3,3 is a simple, connected graph
with 6 nodes (and 9 arcs). It has no cycles of length 3, because this would require two
nodes in one of the two subsets to be adjacent. If it were a planar graph, inequality
(3) would hold, but 9 > 2(6) − 4. Therefore K 3,3 is not planar.
praCTiCe 15 Show that inequality (2) does hold for K 3,3 , which shows that this inequality is a necessary
but not sufficient condition for planarity in graphs with n ≥ 3.
■
The nonplanar graphs K 5 and K 3,3 play a central role in all nonplanar graphs.
To state what this role is, we need one more definition.
Definition homeomorphic Graphs
Two graphs are homeomorphic if both can be obtained from the same graph by
a sequence of elementary subdivisions, in which a single arc x–y is replaced by
two new arcs x–v and v–y connecting to a new node v.
example 15
The graphs in parts (b) and (c) of Figure 6.23 are homeomorphic because each can
be obtained from the graph of Figure 6.23a by a sequence of elementary subdivisions. (However, neither can be obtained from the other by a sequence of elementary subdivisions.)
(c)
(b)
(a)
Figure 6.23
tHeorem KuraTowsKi Theorem
A graph is nonplanar if and only if it contains a subgraph that is homeomorphic
to K 5 or K 3,3 .
We won’t prove this theorem, although one direction is easy to see. If a graph has a
subgraph homeomorphic to the nonplanar graphs K 5 or K 3,3 , then the subgraph—
and hence the entire graph—is nonplanar.
491
A graph that is planar cannot be turned into a nonplanar graph by elementary
subdivisions, and a graph that is nonplanar cannot be turned into a planar graph
by elementary subdivisions (see Exercise 32). As a result, homeomorphic graphs
are either both planar or both nonplanar. The following theorem, due to the Polish
mathematician Kazimierz Kuratowski, characterizes nonplanar graphs.
example 14
K 5 is a simple, connected graph with 5 nodes (and 10 arcs). If it were a planar graph,
inequality (2) of our theorem would hold, but 10 > 3(5) − 6. Therefore, just as our
construction argument showed, K 5 is not planar. K 3,3 is a simple, connected graph
with 6 nodes (and 9 arcs). It has no cycles of length 3, because this would require two
nodes in one of the two subsets to be adjacent. If it were a planar graph, inequality
(3) would hold, but 9 > 2(6) − 4. Therefore K 3,3 is not planar.
praCTiCe 15 Show that inequality (2) does hold for K 3,3 , which shows that this inequality is a necessary
but not sufficient condition for planarity in graphs with n ≥ 3.
■
The nonplanar graphs K 5 and K 3,3 play a central role in all nonplanar graphs.
To state what this role is, we need one more definition.
Definition homeomorphic Graphs
Two graphs are homeomorphic if both can be obtained from the same graph by
a sequence of elementary subdivisions, in which a single arc x–y is replaced by
two new arcs x–v and v–y connecting to a new node v.
example 15
The graphs in parts (b) and (c) of Figure 6.23 are homeomorphic because each can
be obtained from the graph of Figure 6.23a by a sequence of elementary subdivisions. (However, neither can be obtained from the other by a sequence of elementary subdivisions.)
(c)
(b)
(a)
Figure 6.23
tHeorem KuraTowsKi Theorem
A graph is nonplanar if and only if it contains a subgraph that is homeomorphic
to K 5 or K 3,3 .
We won’t prove this theorem, although one direction is easy to see. If a graph has a
subgraph homeomorphic to the nonplanar graphs K 5 or K 3,3 , then the subgraph—
and hence the entire graph—is nonplanar.