Introduction to Graph Theory (18 page)

Corollary 7
. The set of all nonplanar graphs is equal to the set of all graphs that are supergraphs of expansions of
UG
or K
₅
.

Proof
. Let
N
be the set of all nonplanar graphs and
E
be the set of all graphs that are supergraphs of expansions of
UG
or
K
₅
.
N
is a subset of
E
by Kuratowski's Theorem and
E
is a subset of
N
by
Corollary 6
, so
N
=
E
by
Definition 4
.

Corollary 7
is quite a surprise. It says that beneath the apparent chaos of nonplanar graphs there is an order of astounding simplicity. By it we see that the two simplest nonplanar graphs,
UG
and
K
₅
, are essentially the
only
nonplanar graphs, in the sense that they are the building-blocks with which all the others are constructed.

Our original question has been answered. We have penetrated the nature of nonplanarity and have been able to explain it in terms of other concepts that are more easily understandable. It follows that we have also penetrated the nature of planarity. By
Corollary 7
, “nonplanar” means the same as “being a supergraph of an expansion of
UG
or
K
₅
,” so “planar” must mean “not being a supergraph of an expansion of
UG
or
K
₅
.” It is an intellectual delight to find such a simple solution to such a complex problem.

Corollary 7a
. The set of all planar graphs is equal to the set of all graphs that are not supergraphs of expansions of
UG
or
K
₅
.

Determining whether a graph is planar or nonplanar

At the beginning of this chapter, proving a graph to be nonplanar consisted of proving that it could not possibly be drawn in a plane without edge-crossings, a negative procedure that for even the simplest nonplanar graphs was rather tedious (
Theorems 3
and
4
).
Corollary 5
gave us a shorter and more positive method: if we can find a subgraph of a graph
G
that is isomorphic to
UG
or
K
₅
, then that proves that
G
is nonplanar. Unfortunately we had no reason to believe this method would always work. And we soon found that indeed it would
not
always work: the graph of
Figure 66a
is nonplanar but contains no subgraph isomorphic to
UG
or
K
₅
. This discovery led to
Theorem 6
, which in conjunction with
Corollary 5
gave us an improved method for proving a graph nonplanar: if, given a graph G, we can either find a subgraph isomorphic to
UG
or
K
₅
, or we can show that
G
itself is isomorphic to an expansion of
UG
or
K
₅
, then that proves that
G
is nonplanar. Again we had no reason to believe this method would always work, and again it turned out that sometimes it would not: the graph of
Figure 73
is nonplanar, but is neither a supergraph nor an expansion of
UG
or
K
₅
. But by then we had formulated
Corollary 6
, which gave us a third method: if we can find a subgraph of a graph
G
that is isomorphic to an expansion of
UG
or
K
₅
, then that proves
G
is nonplanar. The significance of Kuratowski's Theorem is that by saying every nonplanar graph contains such a subgraph,
it guarantees that the third method will always work
.

Often we will encounter a graph that we want to categorize as being either planar or nonplanar, but which is not obviously either. Here are some guidelines for determining which it is.

1) Before you do anything else, try to draw the graph without edge-crossings. If you succeed that proves it's planar and the matter is settled. If you fail then you know it's probably nonplanar.

2) If you decide the graph is probably nonplanar, the next step is to prove it, which by
Corollary 7
amounts to finding a subgraph that is an expansion of
UG
or
K
₅
. The vast majority of nonplanar graphs contain an expansion of
UG
, so start by looking for that. If, however, the graph does not have at least six vertices with degrees greater than or equal to 3, then it cannot possibly contain an expansion of
UG
and you should go to step 4).

3) Here's how to look for an expansion of
UG
. I don't guarantee that this procedure will unfailingly uncover an expansion of
UG
, as there are a number of choices involved; nevertheless I think it is useful as a search pattern. Pick a vertex whose degree is at least 3, and call it the “first house”. Then find three other vertices with degrees at least 3 (the “utility companies”), from which it is only a short trip along the edges to the first house. Ideally the three utility companies would be joined to the first house by a single edge, but if this is not possible pick them so that you can travel to the first house by a short alternating sequence of edges and vertices. No two of these paths should share a vertex, other than the vertex you have called the “first house”, nor should they share an edge, otherwise the subgraph you are constructing will not untangle into an expansion of
UG
. Mark the paths from the utilities to the first house with jagged lines. Now pick the “second house”, a vertex with degree at least 3 from which you can travel to the three utilities along paths that are, except for their endpoints, disjoint from one another and from the three paths going to the first house. Mark these paths. In a similar fashion pick the “third house” and mark three paths joining it to the three utilities; as before these paths should be, except for their endpoints, disjoint from each other and from the previous six paths. Now extract a subgraph from the original graph by erasing everything that you haven't marked. It is easy to show that such a subgraph is isomorphic to an expansion of
UG
. The three houses correspond to vertices
A, B
, and
C
of
UG
(as originally defined), the three utilities correspond to vertices
X, Y
, and Z, and any other vertices of the subgraph correspond to expansion vertices spliced into the edges of
UG
.

4) Here's how to look for an expansion of
K
₅
. (Of course, the graph must have at least five vertices with degrees greater than or equal to 4, or it cannot possibly contain an expansion of
K
₅
.) Pick a vertex (I'll call it “#1”) having a degree of at least 4 and mark four paths joining it to four other vertices (“#2”, “#3”, “#4”, and “#5”) having degrees that are at least 4. Then from vertex #2 mark three paths leading to vertices #3, #4, and #5; from vertex #3 mark two paths leading to vertices #4 and #5; and from vertex #4 mark a path leading to vertex #5. These ten paths must be mutually disjoint; if they have any edges in common, or any vertices in common other than their endpoints, the subgraph you have marked will not be an expansion of
K
₅
. Extract this subgraph by erasing everything unmarked. It is a simple matter to show that it is isomorphic to an expansion of
K
₅
.

Examples
.
1) I want to know whether or not the graph in
Figure 77
is planar. I start by trying to draw it without edge-crossings. In my first attempt I pull several of the edges to the outside (
Figure 78a
). This reduces the number of crossings to four, and I notice that I can eliminate three of them by bending edge {2,7} and flipping edge {7,8} end over end (
Figure 78b
). Then after staring at
Figure 78b
for a while I notice that I could eliminate the only remaining crossing by moving edge {5,9}. The result, shown in
Figure 79a
, is crossing-free and so the original graph, being isomorphic to the graph of
Figure 79a
, is planar.
Figure 79b
is a less amorphous-looking version of
Figure 79a
.

Figure 77

Figure 78

Figure 79

2)
The vertices of a graph
H
correspond to the squares of a 4 × 4 chessboard, and two vertices are joined by an edge whenever a knight can go from one of the corresponding squares to the other in one move. I have drawn
H
in
Figure 80
(messy, isn't it?) and I want to know whether or not it is planar. I start by trying to draw it without edge-crossings. I fail repeatedly;
Figure 81
is the best I can do. So now I'm virtually certain that
H
is nonplanar. I notice that
H
doesn't contain an expansion of
K
₅
, because it has no vertices of degree 4, so I conclude that
H
must contain an expansion of
UG
. (In any case, I would have searched first for an expansion of
UG
, because expansions of
UG
are more likely and easier to find.)
H
has eight vertices of degree 3 and four of degree 4, so I have twelve vertices from which to choose my houses and utilities. I'll choose vertex 8 at random to be the first house. 8 is joined directly to vertices 2, 10, and 15, and these vertices have degrees greater than or equal to 3, so I'll let them be the three utilities. I'll mark the edges from 8 to 2, 8 to 10, and 8 to 15 (
Figure 82
). Now I have to pick a second house. I'll look for a vertex from which I can travel easily to the three utilities. Vertex 9 seems a likely candidate because it is joined to two of the utilities directly; and I can get from 9 to the third by passing through 7 and 16. So I'll make 9 the second house and mark the paths joining 9 to 2, 9 to 10, and 9 to 15. Finally I need a third house. Almost any vertex with degree at least 3 would do, but I'll pick vertex 3 (because I feel like it) and mark three paths joining 3 to the utilities; the path from 3 to 10 is a single edge, the path from 3 to 2 passes through 5 and 11, and the path from 3 to 15 passes through 12 and 6. This is all displayed in
Figure 82
. Except for the houses and utilities no vertex has been marked more than once, and no edge has been marked more than once, so I know the paths are disjoint and therefore that I'm practically finished. I'll erase every unmarked vertex and edge, extracting from
H
the subgraph
J
drawn in
Figure 83
. In
Figure 84a
I draw an unlabeled version of
UG
and give its houses (the vertices in the top row) the same labels as the houses in
J
, and its utilities (the vertices in the bottom row) the same labels as the utilities in
J
. Then I expand
UG
in accordance with the paths in
J
; for instance, in graph
J
house 9 is joined to utility 10 via 7 and 16, so into the edge {9, 10} of
UG
I'll splice two vertices of degree 2 and label them 7 and 16. Continuing the process I arrive at the expansion of
UG
drawn in
Figure 84b
. The graph in 84b is isomorphic to
J
, which in turn is a subgraph of
H
, so I have shown that
H
is a supergraph of an expansion of
UG
and therefore is nonplanar by either
Corollary 6
or
Corollary 7
.