Introduction to Graph Theory (17 page)

Figure 70

Figure 71

Theorem 6
.
Every expansion of
UG
or
K
₅
is nonplanar
.

Proof
. The proof is a generalization of the argument we used twice in the last section. Let
H
be any expansion of
UG
or
K
₅
. Suppose for the sake of argument that
H
is planar. Then
H
can be drawn in a plane without edge-crossings. Suppose this has been done.

Now let's examine the crossing-free drawing of
H
we are supposing to exist. All the “new” vertices are easy to find because they are all of degree 2, whereas the original vertices all have higher degree (3 if
H
is an expansion of
UG;
4 if
H
is an expansion of
K
₅
). Erase all the new vertices and in each case join the two dangling edges to form a single edge. This reversal of the process that produced
H
will not create any edge-crossings because the vertices we have removed are all of degree 2. Thus our alteration of the crossing-free drawing of
H
is also crossing-free. But our alteration is nonplanar, being either
UG
or
K
₅
. This contradiction shows our supposition to be false, so
H
is nonplanar.

Corollary 6
.
Every supergraph of an expansion of
UG
or
K
₅
is nonplanar
.

Proof
. Let
H
be an expansion of
UG
or
K
₅
and let
G
be a supergraph of
H. H
is nonplanar by
Theorem 6
, so
G
is nonplanar by
Corollary 5
.

Kuratowski's Theorem

We started with the two simplest nonplanar graphs,
UG
and
K
₅
. We used
Corollary 5
to generate infinitely many more, the supergraph: of
UG
and
K
₅
. Then we used
Theorem 6
to generate another infinity of examples, the expansions of
UG
and
K
₅
. Now to this massive infinity of nonplanar graphs
Corollary 6
adds yet another infinitely many the supergraphs of the expansions of
UG
and
K
₅
.

The situation is illustrated in
Figure 72
. The right-hand circle represents the set of all graphs that are supergraphs of
UG
or
K
₅
.
UG
and
K
₅
are themselves contained in this circle because they are supergraphs of themselves. The left-hand circle represents the set of all graphs that are expansions of
UG
or
K
₅
.
UG
and
K
₅
are contained in this circle as well because they are expansions of themselves Otherwise the two circles have nothing in common, because
UG
is the only expansion of
UG
that is also a supergraph of
UG
, and
K
₅
, is the only expansion of
K
₅
that is also a supergraph of
K
₅
(see
Exercise 13
).

Figure 72

The rectangle represents the set of all graphs that are supergraphs of expansions of
UG
or
K
₅
. It contains everything in the two circles, and infinitely many other things besides. It contains the left-hand circle because an expansion of (say)
UG
can be viewed as a supergraph of itself and therefore as a supergraph of an expansion of
UG
. The rectangle contains the right-hand circle because
UG
can be viewed as an expansion of
UG
and so a supergraph of
UG
can be viewed as a supergraph of an expansion of
UG
. And the graph of
Figure 73
is an example of something contained in the rectangle but not contained in either circle.

The graph of
Figure 73
is not an expansion of
UG
because expansions of
UG
have six vertices of degree 3 (the original vertices) and have all other vertices of degree 2 (the new vertices spliced into the edges); but
Figure 73
has a different distribution of degrees. And it's not a supergraph of
UG
because
UG
consists of six vertices each of which is joined to three of the other five, so any supergraph of
UG
would have to contain a collection of six vertices each of which is joined to three of the other five; but since the degrees of vertices 1, 2, 3, and 4 are too small, the only possible collection of six vertices from
Figure 73
is
A
,
B
,
C
,
X
,
Y
,
Z
, and of these
A
,
X
,
C
, and
Z
are only joined to two of the other five. Clearly the graph of
Figure 73
is neither an expansion nor a supergraph of
K
₅
. It is actually a supergraph of an expansion of
UG
. It was formed by first splicing three vertices into the edges of
UG
, creating the expansion of
UG
drawn in
Figure 74
, and then making a supergraph of
Figure 74
by adding a vertex and two edges. The result (
Figure 73
) is nonplanar by
Corollary 6
.

The first nonplanar graphs we discovered were the supergraphs of
UG
and
K
₅
. Then we discovered a second type, the expansions of
UG
and
K
₅
. The graph of
Figure 73
is our first specific example of a third type that includes the other two. Since this third type has resulted from taking supergraphs of expansions of
UG
or
K
₅
, you might wonder if taking expansions of supergraphs of
UG
of
K
₅
would result in a fourth type. As a matter of fact, it wouldn't. Every expansion of a supergraph of
UG
or
K
₅
is also a supergraph of an expansion of
UG
or
K
₅
. For example,
Figure 75
traces the construction of an expansion of a supergraph of
K
₅
, but
Figure 76
shows how the same result can be achieved by taking a supergraph of an expansion of
K
₅
.

Figure 73

Figure 74

If there are still more nonplanar graphs floating around we should try to discover them and compare them to the ones we have now in order to understand what makes these things tick. On the other hand, if a persistent search reveals no additional types of nonplanar graph, we should try to prove a theorem that says there are no more nonplanar graphs to be found. Such a theorem would mean that in constructing the examples we now have, we have already discovered the pattern to nonplanar graphs.

Once more we are faced with the question, “Are there more nonplanar graphs?” That is, “Are there any nonplanar graphs which are not supergraphs of expansions of
UG
or
k
₅
?”

In the early decades of this century mathematicians asked this question, searched for new kinds of nonplanar graphs, and failed to find any. So they took the next step and tried to prove that there were none to be found. In 1930 a mathematician named Kasimir Kuratowski succeeded in doing this.

Figure 75

Figure 76

Kuratowski's Theorem
.
Every nonplanar graph is a supergraph of an expansion of
UG
or
K
₅
.

The proof is rather involved, and I will omit it. It may seem that in citing Kuratowski's Theorem without proof I am pulling a rabbit out of a hat, much as I did with the Jordan Curve Theorem. The situations, however, are not parallel. I
couldn't
prove the Jordan Curve Theorem without another book. I
could
prove Kuratowski's Theorem in considerably less space, maybe thirty pages, but I have decided not to because it doesn't seem worth it. Apart from being long, the proof is highly specialized and has almost no bearing on the other topics we will be taking up. Suffice it to say that Kuratowski's Theorem has been proved, and that if you wish to see a proof you can find one in Harary's
Graph Theory
, pp. 108–113. (At first you may find Harary's proof difficult because it is rather condensed. But if you are willing to spend the time necessary to look up and absorb all unfamiliar concepts and symbols, you should be able to follow it well enough.)