Introduction to Graph Theory (24 page)

Case 2
.
G
has three or more vertices.

Suppose for the sake of argument that every vertex of
G
has degree ≥ 6. Then, numbering the vertices of
G
from 1 to
v,
we can make the series of statements

Hence 6
v
, the sum of the first column, is less than or equal to 2
e
, which is the sum of the second column—see
Exercise 11
of Chapter 2. Dividing both sides of this inequality by 2 gives us 3
v
≤
e
. But by
Theorem 11
,
e
≤ 3
v
− 6, so 3
v
≤ 3
v
− 6, a contradiction. Therefore our supposition must be false and
G
must have at least one vertex with degree ≤ 5.

Corollary 13
.
If
G
is planar then
G
has a vertex of degree
≤ 5.

Proof.
If
G
is planar and connected it has a vertex of degree ≤ 5 by the theorem; so let
G
be planar and disconnected.

Disconnected graphs are in two or more connected
pieces, as we have seen. Let
J
be any such piece. Then
J
is in its own right a planar (by
Theorem 5
) connected graph, and so by
Theorem 13
J
has a vertex of degree ≤ 5. This vertex is also a vertex of
G
and so
G
has a vertex of degree ≤ 5.

Algebraic topology

In the last section there surfaced two new proofs of the nonplanarity of
UG
and
K
₅
. The purpose of this section is to shed some light on the nature of these new proofs.

Euclidean geometry is concerned with the “metric” properties of figures, that is those properties that can be measured: lengths of lines, sizes of angles, areas, etc. From a metric perspective
Figure 102
contains five different objects.

Topology
(not to be confused with “topography”) is a sort of generalized geometry. It is a relatively new branch of mathematics wherein the first four objects in
Figure 102
are considered to be “the same”. Each of these four has a property shared by the other three, but not by the fifth. To see what the property is, imagine that the first object is made of extremely pliable rubber. The rules are that we may stretch, shrink, or otherwise distort the rubber as much as we want, but we may not tear it or fold it back onto itself. Under these rules we could transform the first triangle successively into the right triangle, the square, and the circle, but not into the fifth object. A transformation of one figure into another by this process is called a “continuous deformation”. A topologist considers figures that can be continuously deformed into one another to be equivalent; or in other words, a topologist studies only those properties of figures that are preserved by continuous deformations. Being a “continuous simple closed curve” is an example of such a property (see page 66), and thus the Jordan Curve Theorem is an example of a topological theorem. It says that when any object topologically equivalent to a circle is embedded in a plane, it cuts the plane into two pieces.

Figure 102

Henri Poincaré, one of the founders of the modern phase of topology, described the subject as follows (translation by Edna Kramer, quoted by her in
The Nature and Growth of Modern Mathematics
, vol. 2, p. 326):

“[Topology] is a purely
qualitative
subject where quantity is banned. In it two figures are always equivalent if it is possible to pass from one to the other by a continuous deformation, whose mathematical law can be of any sort whatsoever as long as continuity is respected. Thus a circle is equivalent to any sort of closed curve but not to a straight-line segment, because the latter is not closed. Suppose that a model is copied by a clumsy craftsman so that the result is not a duplicate but a distortion. Then the model and the copy are not equivalent from the point of view of metric geometry. . . . The two figures are, however, topologically equivalent.

It has been said that geometry is the art of
applying good reasoning to bad diagrams. This is not a joke but a truth worthy of serious thought. What do we mean by a poorly drawn figure? It is one where proportions are changed slightly or even markedly, where straight lines become zigzag, circles acquire incredible humps. But none of this matters. An inept artist, however, must
not
represent a closed curve as if it were open, three concurrent lines as if they intersected in pairs, nor must he draw an unbroken surface when the original contains holes.”

There's an old anecdote on topology that runs something like this. A topologist enters a coffee shop, orders coffee and a doughnut, and is served. Preoccupied with topological theorems, he takes a bite out of his coffee cup and has to finish his thoughts in a nearby emergency ward. His mistake is somewhat understandable as a doughnut and coffee cup are topologically equivalent, as sketched in
Figure 103
.

Algebra
is another branch of mathematics; it studies sets on which there have been defined things called “operations”. An operation on a set is a rule whereby two or more elements of the set can be combined to form another element of the set. High school algebra is the algebra of one specific set, the set of real numbers, and four specific operations defined on that set, addition, subtraction, multiplication, and division. High school algebra is only the tip of the algebraic iceberg.

Figure 103

It so happens that topological problems are somewhat harder
to solve than algebraic ones. There is a further factor that algebra has been studied for far longer than topology, so there has been more time to develop algebraic techniques. And so, to make progress in topology while at the same time taking advantage of the advanced state of algebraic knowledge, mathematicians have devised a branch of topology known as
algebraic topology,
wherein algebraic methods are applied to topological problems. In algebraic topology the procedure runs something like this: take a topological problem and if possible convert it into an algebraic problem; try to solve the algebraic problem; if you succeed, reconvert the algebraic solution into topological terms, and the result will be a topological solution to the original problem.

This technique of convert-solve-reconvert is not unique to algebraic topology. It is in fact one of the oldest methods in mathematics. For example, if asked to express the product of CLIII and XXIX as a Roman numeral, you would probably
convert
the original problem CLIII × XXIX into the corresponding Hindu-Arabic numeral problem 153 × 29,
solve
the Hindu-Arabic problem in the standard way, and then
reconvert
the Hindu-Arabic solution 4437 into the Roman numeral MMMMCCCCXXXVII which is the solution to the original problem. Analytic geometry, developed in 1637 by René Descartes, is another example of the convert-solve-reconvert technique. In analytic geometry we take a problem in geometry, convert it into a problem about a system of equations, solve the system of equations, and then reconvert the “analytic” (actually algebraic) solution back into geometric terms.

In order to use the convert-solve-reconvert technique there must be a
means
whereby problems in one area of mathematics can be converted into problems in another area. In the case of the Roman numeral problem the means was the familiar one learned in grammar school. In the case of analytic geometry the means is to associate with every geometric point a pair (
x
,
y
) of real numbers called the “coordinates” of the point; straight lines are thereby converted into equations, triangles into systems of equations, and so on.

In the last section when we proved anew that
UG
and
K
₅
are nonplanar, we were doing a bit of algebraic topology. Graph theory is a small part of topology, high school algebra is a small part of algebra, and Euler's Formula is the means whereby we converted problems in graph theory to problems in high school algebra. In
Corollary 11
for example, the statement is purely topological, yet the proof, which is based on Euler's Formula via
Theorem 11
, is purely algebraic. Similar remarks hold for
Corollary 12
. In these situations our work was algebraic but its import was topological.

In the sequel we will be doing more algebraic
topology, so it might be well at this point to mention that subject's chief advantage and chief disadvantage. The advantage is that an algebraic proof of a topological theorem is shorter than a topological proof, which may not even exist. The disadvantage is that an algebraic proof is less conducive to real understanding.

Take for example our two proofs that
UG
is nonplanar. The first proof (
Theorem 3
) was purely topological. It was quite long, and even at that was essentially incomplete, for we accepted the Jordan Curve Theorem without proof. The second proof (
Corollary 12
) was purely algebraic, quite short, and complete. Yet the second proof is somehow mysterious. After reading it we wonder what happened. Our intellect is convinced but our intuition isn't. We leave the second proof with no real
feeling
as to why
UG
is nonplanar. The proof is so concise that all intuitive handles have been squeezed out. Deep down our intuition wonders if it hasn't been tricked. There is none of this mystery in the first proof. The Jordan Curve Theorem is so intuitively “obvious” that its rigorous justification is not missed. Because of the length of the proof, and the diagrams, and the fact that each step is basic and not dependent on an elaborate substructure of previous theorems, our intuition is satisfied along with our intellect.

Most people would judge that the advantage outweighs the disadvantage. And for people who like mystery stories, or who fantasize being seduced by a mysterious stranger, what I have called the “disadvantage” isn't a disadvantage at all.

Exercises

  
1.
  
N
₁
is certainly planar, and we proved on page 98 that it is connected. Prove now that it is polygonal by proving that the statement “every edge of
N
₁
borders on two different faces” is true
.

  
2
.
Find the error in the following “proof”:

Theorem
.
If A is a set of horses, then all the horses in A are of the same color.

Proof.
Let
S
be the statement, “if
A
is a set of
n
horses, then all the horses in A are of the same color.”
S
is a statement about positive integers
n
, and we shall prove that
S
is true for every positive integer by the principle of mathematical induction; this will establish the theorem. The first step is to prove