Introduction to Graph Theory

Richard J. Trudeau

• Publisher: Dover Publications
• Year: 2013
• ISBN:
  9780486318660
• Topic: Mathematics
• Subtopic: Mathematics General
• Index: Mathematics

Aimed at "the mathematically traumatized, " this text offers nontechnical coverage of graph theory, with exercises. Discusses planar graphs, Euler's formula, Platonic graphs, coloring, the genus of a graph, Euler walks, Hamilton walks, more. 1976 edition.

1. PURE MATHEMATICS

Introduction

This book is an attempt to explain pure mathematics. In this chapter we’ll talk about it. In Chapters 2–8 we’ll do it.

Most pre-college mathematics courses are oriented toward solving “practical” problems, problems like these:

A train leaves Philadelphia for New York at 3:00 PM and travels at 60 mph. Another train leaves New York for Philadelphia at 3:30 PM and travels at 75 mph. If the distance between the cities is 90 miles, when and at what point will the trains pass?

If a 12-foot ladder leaning against a house makes a 75° angle with the ground, how far is the foot of the ladder from the house and how far is the top of the ladder from the ground?

Mathematics that is developed with an eye to practical applications is called “applied mathematics”. With the possible exception of Euclidean geometry, pre-college mathematics is usually applied mathematics.

There is another kind of mathematics, called “pure mathematics”, which is a charming little pastime from which some people derive tremendous enjoyment. It is also the basis for applied mathematics, the “mathematics” part of applied mathematics. Pure mathematics is real mathematics.

To understand what mathematics is, you need to understand what pure mathematics is. Unfortunately, most people have either seen no pure mathematics at all, or so little that they have no real feeling for it. Consequently most people don’t really understand mathematics; I think this is why so many people are afraid of mathematics and quick to proclaim themselves mathematically stupid.

Of course, since pure mathematics is the foundation of applied mathematics, you can see the pure mathematics beneath the applications if you look hard enough. But what people see, and remember, is a matter of emphasis. People are told about bridges and missiles and computers. Usually they don’t hear about the fascinating intellectual game that lies beneath it all.

Earlier I implied that Euclidean geometry—high school geometry— might be an example of pure mathematics. Whether it is or not again depends on emphasis.

Euclidean geometry as pure mathematics

What we call “Euclidean geometry” was developed in Greece between 600 and 300 B.C., and codified at the end of that period by Euclid in The Elements. The Elements is the archetype of pure mathematics, and a paradigm that mathematicians have emulated ever since its appearance. It begins abruptly with a list of definitions, followed by a list of basic assumptions or “axioms” (Euclid states ten axioms, but there are others he didn’t write down). Thereafter the work consists of a single deductive chain of 465 theorems, including not only much of what was known at that time of geometry, but algebra and number theory as well. Though that’s quite a lot for one book, people who read The Elements for the first time often get a feeling that things are missing: it has no preface or introduction, no statement of objectives, and it offers no motivation or commentary. Most strikingly, there is no mention of the scientific and technological uses to which many of the theorems can be put, nor any warning that large sections of the work have no practical use at all. Euclid was certainly aware of applications, but for him they were not an issue. To Euclid a theorem was significant, or not, in and of itself; it did not become more significant if applications were discovered, or less so if none were discovered. He saw applications as external factors having no bearing on a theorem’s inherent quality. The theorems are included for their own sake, because they are interesting in themselves. This attitude of self-sufficiency is the hallmark of pure mathematics.

The Elements is the most successful textbook ever written. It has gone through more than a thousand editions and is still used in some parts of the world, though in this country it was retired around the middle of the nineteenth century. It is amazing that it was used as a school text at all, let alone for 2200 years, as it was written for adults and isn’t all that easy to learn from.

Of the modern texts that have replaced The Elements, many are faithful to its spirit and present geometry as pure mathematics, ars gratia artis. There are others, however, that have sandwiched around Euclid’s work long discussions of the “relevance” and “practicality” of geometry, complete with pictures of office buildings and space capsules and the suggestion that geometry is primarily a branch of engineering. Of course, applied geometry is a perfectly valid science, but I can’t help objecting to such books on the ground that they rob school children of their only encounter with pure mathematics.

Despite this problem, in the next section I shall use Euclidean geometry as an example of pure mathematics, as it is the branch of pure mathematics with which you are most likely to be familiar.

Games

Basically pure mathematics is a box of games. At last count it contained more than eighty of them. One of them is called “Euclidean geometry”. In this section I will compare Euclidean geometry to chess, but you won’t have to be a chessplayer to follow the discussion.

Games have four components: objects to play with, an opening arrangement, rules, and a goal. In chess the objects are a chessboard and chessmen. The opening arrangement is the arrangement of the pieces on the board at the start of the game. The rules of chess tell how the pieces move; that is, they specify how new arrangements can be created from the opening arrangement. The goal is called “checkmate” and can be described as an arrangement having certain desirable properties, a “nice” arrangement.

In Euclidean geometry the objects are a plane, some points, and some lines. The plane corresponds to a chessboard, the points and lines to chessmen. The opening arrangement is the list of axioms, which are accepted without proof. The analogy with the opening arrangement of chessmen may not be apparent, but it is quite strong. First, the opening arrangement of chessmen is given; to play chess you must start with that arrangement and no other. In the same way the axioms of Euclidean geometry are given. Second, the opening arrangement of chessmen specifies how the objects with which the game is played are related at the outset. This is exactly what the axioms do for the game of Euclidean geometry; they tell us, for example, that points and lines lie in the plane, that through two points there passes one and only one line, etc. The rules of Euclidean geometry are the rules of formal logic, which is nothing but an etherealized version of the “common sense” we absorb from the culture as we grow up. Its rules tell us how statements can be combined to produce other statements. They tell us, for example, that the statements “All men are mortal” and “Plato is a man” yield the statement “Plato is mortal.” (The example is Aristotle’s. He wrote the first book on logic by recording patterns of inference he saw people using every day.) In particular the rules of logic tell us how to create, from the opening arrangement (the list of axioms), new arrangements (called “theorems”). And the goal of Euclidean geometry is to produce as many “nice” arrangements as possible, that is to prove profound and surprising theorems. Checkmate terminates a chessmatch, but Euclidean geometry is open-ended.

Games have one more feature in common with pure mathematics. It is subtle but important. It is that the objects with which a game is played have no meaning outside the context of the game.

Chessmen, for example, are significant only in reference to chess. They have no necessary correspondence with anything external to the game. Of course, we could interpret the pieces as regiments at the First Battle of the Marne, and the board as French countryside. Or an interpretation could be brought about by a wager, say each piece represents $5.00 and losing it means paying that amount. But no such correspondence between the game and things outside the game is necessary.

You may balk at this, since, for historical reasons, chessmen have names and shapes that imply an essential correspondence with the external world. The key word is “essential”; there is indeed a correspondence, but it is inessential. After all, chessmen require names of some sort, and must be shaped differently to avoid confusion, so why not call them “kings”, “queens”, “bishops”, “knights”, etc., shape them accordingly, and trade on the image of excitement and competition thereby created? Doing so is harmless and makes the game more popular. But this particular interpretation of the game, like all others, has nothing to do with chess per se.

Here’s an example. Suppose we substitute silver dollars for kings, half-dollars for queens, quarters for bishops, dimes for knights, nickels for rooks, pennies for pawns, and an eight-by-eight array of chartreuse and violet circles for the standard board, but otherwise follow the rules of chess. Such a game would look strange and even sound strange—“pawn to king four” would now be “penny to silver dollar four”—but surely if we were to play this apparently unfamiliar game, there would be no doubt that we are playing the familiar game of chess. Indeed, chessmasters sometimes play without a board or pieces of any kind; they merely announce the moves and keep track in their heads. Two such people are still playing chess, for after all they say they are, and they certainly should know.

It appears then that the essence of chess is its abstract structure. Names and shapes of pieces, colors of squares, whether the “squares” are in fact square, even the physical existence of board and pieces, are all irrelevant. What is relevant is the number and geometric arrangement of the “squares”, the number of types of piece and the number of pieces of each type, the quantitative-geometric power of each piece, etc. Everything else is a visual aid or a fairy tale.

So it is with pure mathematics. Euclid’s words “plane”, “point”, and “line” suggest that geometry deals with flat surfaces, tiny dots, and stretched strings, but this implied interpretation of geometry is only that. It is analogous to the interpretation of chess as a battle. Geometry is no more a study of flat surfaces and dots than chess is a military exercise. As in any game, the objects geometers play with, and consequently their arrangements—the axioms and theorems—have no necessary correspondence with things external to the game.

In support of this let me point out that geometers never define the words “plane”, “point”, or “line”. (Euclid offered an intuitive explanation but did not actually define them; moderns leave the words undefined.) So no one knows what planes, points, or lines are, except to say that they are objects which are related to one another in accordance with the axioms. The three words are merely convenient names for the three types of object geometers play with. Any other names would do as well. Were we to attack Euclid’s Elements with an eraser and remove every occurrence of the words “plane”, “point”, and “line”, replacing them respectively with the symbols “#”, “$”, and “?”, the result would still be The Elements and the game would still be geometry. To a casual observer the vandalized Elements wouldn’t look like geometry; what had been “two points determine one and only one line” would now be “two $’s determine one and only one ?”. But then two people hunched over a board of chartreuse and violet circles, littered with coins, doesn’t look like a chessmatch. The game would still be geometry because it would be structurally identical to geometry. And were we to further maim The Elements by erasing all the diagrams, it still wouldn’t make a difference. Geometric diagrams are to geometers what board and pieces are to chessmasters: visual aids, helpful but not indispensable.

Why study pure mathematics?

There emerges from the foregoing an image of pure mathematics as a meaningless intellectual pastime. Yet carved over the door to Plato’s Academy was the admonition, “Let no one ignorant of geometry enter here!” And pure mathematics has been held in the highest regard ever since. It would seem to have no more to recommend its inclusion in school curricula than, for instance, chess, yet it is universally favored by academics over other games. I shall give three reasons for this.

Pure mathematics is applicable. Because pure mathematics has no inherent correspondence with the outside world, we are free to make it correspond, to interpret it, in any way we choose. And it so happens—this is the interesting part—that most branches of pure mathematics can be interpreted in such a way that the axioms and theorems become approximately true statements about the external world. In fact, some branches have several such interpretations.

Pure mathematics that has been made to correspond in this way to the world outside is called “applied mathematics”. Pure mathematics is Euclid saying “three $’s not on the same ? determine a unique #.” Applied mathematics is a surveyor reading Euclid, interpreting and “#” in a way that seems in accord with the axioms, and concluding that a tripod would be the most stable support for his telescope.

On one level, the applicability of pure mathematics is no surprise. Just as chess (as we know it) has been modeled on certain aspects of medieval warfare, even though strictly speaking the game has nothing to do with warfare, so too most branches of pure mathematics have started as models of physical situations. A branch of pure mathematics utterly lacking in significant interpretations would be boring to the community of pure mathematicians and would soon die out from lack of interest. Though they are unconcerned with applications as such, pure mathematicians are like most people in that they find it hard to be enthusiastic about something unless, under some aspect at least, it has the spontaneous appearance of truth.

But on a deeper level, the applicability of pure mathematics is quite mysterious. It’s true that pure mathematics often originates with an abstraction from the physical world, as geometry begins with idealized dots and strings and tabletops, but the tie is only historical. Once the abstractions have been made the mathematical game comes into independent existence and evolves under its own laws. It has no necessary correspondence with the original physical situation. The mathematician does not deal with physical objects themselves, but with idealizations that exist independently and differ from their physical counterparts in a great many respects. And entirely within his own mind, the mathematician subjects these abstractions to a reflective, self-analytic process, a process in which he is trying to learn about himself, to learn what in a sense he already knows. This process is strictly internal to a human mind—a Western mind at that—and so is presumably different from whatever the process by which the physical situation evolves; yet when the mathematician compares his results to outside events, he often finds that nature has evolved to a state remarkably like his mathematical model. That the universe is so constructed has seemed uncanny to many famous mathematicians and scientists...

Table of contents

• Cover
• Half Title
• Title Page
• Copyright Page
• Dedication
• Contents
• Preface
• 1. Pure Mathematics
• 2. Graphs
• 3. Planar Graphs
• 4. Euler’s Formula
• 5. Platonic Graphs
• 6. Coloring
• 7. The Genus of a Graph
• 8. Euler Walks and Hamilton Walks
• Afterword
• Solutions to Selected Exercises
• Index
• Special symbols