Introduction to Graph Theory (14 page)

But in principle, as well as practice, it is difficult to demonstrate nonplanarity. A graph is nonplanar if drawing the graph without edge-crossings is impossible, so we are required to prove the impossibility of performing that task—a tall order.

Example
.
The graphs of
Figure 58b
and
c
) are nonplanar, but for now you will have to take my word for it. You might try to draw these graphs without edge-crossings and if you do your failures will incline you to believe me. But you should not allow yourself to be convinced by repeated failures, for how can you be sure you just haven't been clever enough to make a crossing-free drawing? Of course, you can systematize your attempts and draw edges in all possible ways, but for any moderately complicated graph the number of possibilities is quite large, in which case you might overlook one. In general the claim that a graph is nonplanar needs backing up by rigorous proof.

Figure 57

Figure 58

Assuming for the moment that the graphs of
Figure 58b
and
c
) are indeed nonplanar, we see that some graphs are planar and others aren't. We might ask, “Why?” Or in expanded form, “What is it about the structure of a graph that makes it planar or nonplanar; is there some specific feature that we can look for?” In this chapter we shall try to answer this question.

Perhaps a reasonable first step toward finding an answer would be to examine a large number of planar and nonplanar graphs, hoping to detect a pattern. There is no shortage of planar graphs. By never allowing edges to cross, you could draw fifty in ten minutes. But genuine (proven) examples of nonplanar graphs are so far nonexistent, since impossibility is nigh impossible to prove. Therefore we shall begin our research by trying to prove that certain graphs which seem to be nonplanar are in fact nonplanar.

UG
,
K
₅
, and the Jordan Curve Theorem

We might as well start by proving that Dudeney's puzzle
UG
is nonplanar. To so do we shall yank a theorem and corollary (a “corollary” is a theorem associated with another theorem from which it can be easily derived) from an advanced level of another branch of mathematics. The theorem is named after the French mathematician Camille Jordan (1838–1922) who first enunciated it in 1899.

Jordan Curve Theorem
.
If
C
is a continuous simple closed curve in a plane
,
then
C
divides the rest of the plane into two regions having
C
as their common boundary. If a point P in one of these regions is joined to a point Q in the other by a continuous curve L in the plane, then L intersects C
.

Corollary
.
If
C
is a continuous simple closed curve in a plane and two points of
C
are joined by a continuous curve L in the plane having no other points in common with
C
, then except for its endpoints L is entirely contained in one of the two regions determined by C
.

Please don't panic. The theorem and corollary actually say very simple things, though this is obscured by technical jargon. A “continuous curve” is roughly (we haven't the space to do better than “roughly”) an unbroken one-dimensional figure, something one could draw with a pencil without lifting the pencil from the paper. Don't be misledby the word “curve”; it is a technical term and pertains to a wide variety of things, including straight lines. For example the five drawings of
Figure 59
are continuous curves. A continuous curve is
closed
if the starting point and ending point are the same; thus only c), d), and e) of
Figure 59
are continuous closed curves. And a continuous closed curve is
simple
if no point other than the starting point is repeated, and the starting point itself is repeated only once. So only e) of
Figure 59
is a continuous simple closed curve.
Figure 60
has two more examples of continuous simple closed curves. Notice that “simple” in the mathematical sense is not the same as “simple” in everyday usage—
Figure 60b
is mathematically “simple”.

Roughly then, a continuous simple closed curve is something you can make out of a rubber band without cutting it or folding it back onto itself. The Jordan Curve Theorem says that any such thing embedded in a plane cuts the plane into two regions—the inside and the outside—and that any unbroken curve drawn in the plane from a point inside to a point outside must somewhere cross the rubber band. The corollary says that if two points on the rubber band are joined by an unbroken curve in the plane that doesn't touch the rubber band anywhere else, then that unbroken curve must be either entirely inside the rubber band or entirely outside it.

Figure 59

Figure 60

Once they have been translated into plain English the Jordan Curve Theorem and its corollary are painfully obvious. But to a pure mathematician everything that can possibly be proved, no matter how “obvious”, requires proof. Remember Russell's Paradox. Sets were once thought to be “obviously” simple things.

As a matter of fact all known proofs of the Jordan Curve Theorem are quite difficult to follow and probably not one in a hundred professional mathematicians has ever seen such a proof. Jordan himself couldn't prove the Jordan Curve Theorem! A few years after his theorem appeared in print, the “proof” he had published along with it was shown to be invalid. Decades passed before another mathematician finally succeeded in constructing a valid proof.

You may wonder at the problems mathematicians have had with the Jordan Curve Theorem, since what it asserts is so “obvious”. It often happens in mathematics that the most “obvious” theorems have the most difficult proofs. Perhaps this is because when working with basics there are few concepts to work with and few previously proved theorems.

At any rate, the Jordan Curve Theorem has been included in this book both as an example of the lengths to which mathematicians are prepared to go in pursuit of “rigor”, and as a means for making our proof of the next theorem as valid as possible under present mathematical standards.

Theorem 3
.
UG is nonplanar
.

Proof
. The utility graph can be represented as in
Figure 61a
. We shall try to draw it without edge-crossings. Then we shall invoke first the corollary and then the Jordan Curve Theorem itself to show that one edge-crossing, despite our efforts, is unavoidable.

Let
C
denote the object in
Figure 61b
. Note that
C
is a continuous simple closed curve in the plane. Connect
A
to
Z
,
B
to
Y
, and
C
to
X
by continuous curves lying in the plane and having no other points in common with C. We shall denote these curves “{
A
,
Z
}”, “{
B
,
Y
}”, and “{
C
,
X
}”, but for the present we shall leave them out of the diagram.

Figure 61

Applying the corollary in turn to
C
and {
A
,
Z
},
C
and {
B
,
Y
}, and
C
and {
C
,
X
}, we conclude that each of {
A
,
Z
}, {
B
,
Y
}, and {
C
,
X
} is—except for its endpoints—either entirely inside
C
or entirely outside
C
.

If you had three golf balls and two boxes, and put each ball into one or the other of the boxes, the result would be that exactly one of the boxes would contain two or more balls. In this situation we have curves instead of golf balls and regions instead of boxes, but the so-called “pigeonhole principle” is the same, so we are bound to consider two cases.

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

Say that {
A
,
Z
} and {
B
,
Y
} are the two curves definitely inside
C
. It's true that we are restricting ourselves to a specific situation, but the following argument would hold for any other two of the three curves.

C
with {A, Z} inside it has been drawn in
Figure 62a
. At this point it is in some sense “obvious” that
{B, Y}
cannot also be drawn inside
C
without an edge-crossing. But appeals to intuition are mathematically suspect, so we will add to the picture only what we know for sure, namely that {
B
,
Y
} leaves
B
and goes inside
C
and comes from the inside of
C
to end at
Y
. This has been done in
Figure 62b
.

Now let
Q
be a point on the curve
BY
near enough to
B
so that there are no edge-crossings between
B
and Q. Then
AZBXA
is a continuous simple closed curve in the plane,
Q
is a point inside,
Y
is a point outside, so by the Jordan Curve Theorem any continuous curve in the plane joining
Q
to
Y
intersects
AZBXA
. Since {
B
,
Y
} is such a curve we conclude that {
B
,
Y
} cannot be drawn without crossing another edge. For this case at least we have proved that
UG
cannot be drawn in a plane without edge-crossings.