Introduction to Graph Theory (15 page)

Figure 62

Case 2
. There are at least two curves outside
C
.

Say they are {
A
,
Z
} and {
C
,
X
}. The argument is similar to Case 1. Draw
C
with {
A
,
Z
} outside it, draw both ends of {
C
,
X
}, and let
Q
be a point on {
C
,
X
} near enough to
C
so that there are no edge-crossings between
C
and
Q
. See
Figure 62c
.
AYCZA
is a continuous simple closed curve in the plane, Q is inside, × is outside, therefore by the Jordan Curve Theorem every continuous curve in the plane joining
Q
to × must intersect
AYCZA
. {C, X} is such a curve, hence cannot be drawn without crossing another edge. In this case too,
UG
cannot be drawn in a plane without edge-crossings. As there are no more cases, the theorem is proved.

In some sense
UG
is the simplest nonplanar graph, as all others have more edges. In another sense
K
₅
is the simplest nonplanar graph, as all others have more vertices.

Theorem
4.
K
₅
is nonplanar
.

Proof
. A simple extension of the proof of the last theorem. Let
C
be the object of
Figure 63a
.
C
is a continuous simple closed curve in a plane. Connect 1 to 3, 1 to 4, 2 to 4, 2 to 5, and 3 to 5 by continuous curves in the plane having no other points in common with
C
. Applying the corollary to
C
and each of these five curves in turn, we see that each of these curves is either, except for its endpoints, entirely inside
C
or entirely outside
C
.

Figure 63

Invoking the pigeonhole principle, this time with five golf balls and two boxes, we conclude that either the inside of
C
or the outside of
C
contains three or more of the five curves. As before there are two cases to consider.

Case
1. There are at least three curves inside
C
.

Say they are {1,3}, {1,4}, and {3,5}; the following argument would hold as well for any other selection. Note that it is possible to select from the three curves two that share a vertex:
Exercise 1
says that this must always happen. And so from the three curves we select two sharing a vertex and draw them inside
C
. Adding the ends of the third curve results in something like
Figure 63b
.

Let
Q
be a point on the curve {1,4} near enough to 4 that there are no edge-crossings between
Q
and 4. 3453 is a continuous simple closed curve in the plane,
Q
is inside, 1 is outside, so by the Jordan Curve Theorem {1,4}—being as it is a continuous curve in the plane joining
Q
to 1—must intersect 3453. Thus for this case
K
₅
cannot be drawn in a plane without edge-crossings.

Case 2
. There are at least three curves outside
C
.

I leave the proof of this case to you.

We have invested thus far quite a bit of time and energy, the result being a grand total of two nonplanar graphs. At this rate it will be some time before we have enough specimens for serious research, but fortunately there is a simple theorem we can use to generate infinitely many nonplanar graphs.

Theorem 5
.
Any subgraph of a planar graph is planar
.

Proof
. Let
G
be any planar graph. A planar graph can be drawn in a plane without edge-crossings, so let us suppose that this has already been done to
G
.

A subgraph of
G
is the result of selective erasing. If no edge or vertex of
G
is removed the subgraph obtained is
G
itself, which is planar by hypothesis. Otherwise some edges and/or vertices of
G
are actually erased. But erasing edges and/or vertices can never create an edge-crossing. So regardless of how much erasing is done, the subgraph obtained will be without edge-crossings and therefore be planar.

Definition 19
. If a graph
H
is a subgraph of a graph
G
, we will also say that
G
is a
supergraph
of H.

This definition doesn't present anything new; “
G
is a supergraph of
H
” means exactly the same thing as “
H
is a subgraph of
G
.” Its only purpose is that it will make some of our statements less complicated.

Corollary 5
. Every supergraph of a nonplanar graph is nonplanar
.

Proof
. This is just
Theorem 5
stated in apparently different but logically equivalent form. Let
G
be a supergraph of a nonplanar graph
H
. If
G
were planar then
H
, being a subgraph of
G
, would be planar by
Theorem 5
. But
H
is nonplanar, so
G
must be nonplanar too.

Since a subgraph is the result of selective erasing it follows that a supergraph is the result of selective augmentation. Given a graph
G
you can form a supergraph of
G
by adding new vertices and/or connecting nonadjacent (new or old) vertices. But as before there are two catches. First, you needn't add anything, since every graph is a supergraph of itself. Second, you must never put a new vertex on an old edge, for then you are actually replacing that edge by two new ones plus a vertex, so the two formerly adjacent vertices are no longer adjacent, and the resulting graph may not have
G
as a subgraph. For example the graph of
Figure 64a
is not a supergraph of
Figure 64b
; using only an eraser you can never make
C
₄
look like
K
₃
.

Applying the selective augmentation process to a graph
G
, it is clear that there is no end of possibilities. Every graph has infinitely many supergraphs. In particular there are infinitely many supergraphs of
UG
and infinitely many supergraphs of
K
₅
, and all these are guaranteed nonplanar by
Corollary 5
. Despite the fact that some of the supergraphs of
UG
are also supergraphs of
K
₅
, and vice versa, we are still in possession of infinitely many nonplanar graphs.

Figure 64

Examples
.
1)
Figure 65a
is nonplanar because it is a supergraph of
UG
.

2)
Figure 65b
is nonplanar because it is a supergraph of
K
₅
.

3)
Figure 65c
is nonplanar because it is a supergraph of both.

4)
Figure 65d
is nonplanar because it is a supergraph of both.

5) For
v
≥ 6,
K
_v
is nonplanar because it is a supergraph of both.

So here we are with infinitely many nonplanar graphs. We wanted them so that we could examine their structure and perhaps detect a pattern of some kind. But the only obvious pattern—that they are all supergraphs of
UG
or
K
₅
—is no help, because that's how we produced these examples in the first place. So it seems that we should start looking around for more nonplanar graphs.

Figure 65

Are there more nonplanar graphs?

At this point every nonplanar graph we know of is a supergraph of
UG
or
K
₅
. The natural question is, “Are there any more?” If we find some we can compare them to the ones we now have and try to discern properties common to the two groups. Any such properties not shared by planar graphs would be bound up with the inner workings of nonplanarity and we would be that much closer to understanding what makes graphs nonplanar. On the other hand, if a persistent search fails to uncover any new nonplanar graphs, we should suspect that there are no more to be found and should turn our efforts toward proving a theorem that says, “A graph is nonplanar if and only if it is a supergraph of
UG
or
K
₅
.” Proving such a theorem would mean that the only pattern to nonplanar graphs is the one we've already noticed. This would answer the question posed at the beginning of the chapter and, its purpose accomplished, the chapter would contentedly expire.

But a glance at the table of contents shows that this chapter doesn't end for some time, so it seems that indeed there are more nonplanar graphs to be found. It would be instructive if, at the end of this paragraph, you were to put the book away and search for some. Remember the goal: a graph that seems nonplanar—we can worry about proving that later—but is not a supergraph of
UG
or
K
₅
. Such things do exist, and some are quite simple. There is one with
v
= 6 and
e
= 11, another with
v
= 7 and
e
= 10.

Welcome back. The graphs of
Figure 66
are nonplanar, and neither is a supergraph of
UG
or
K
₅
. There are infinitely many other such graphs, some of which you may have discovered, but these two are the simplest, in the following sense. The first has fewer vertices (six) than any other “new type” of nonplanar graph, and the second has fewer edges (ten) than any other “new type” of nonplanar graph.