Introduction to Graph Theory (13 page)

25.
  
Use the technique of
Exercise 24
to prove that the graphs of
Figure 46
are not isomorphic.

26.
  
Draw all graphs having
v
= 5. There are 34 of them. (Imitate the procedure I used in the text to find all graphs with
v
= 4.)

27.
  
In the table on page 54, the numbers in the second column are mostly even. If we ignore the first row on the ground that
v
= 1 is such a trivial situation that its uniqueness is unremarkable, that leaves
v =
4 as the only number of vertices listed for which there are an odd number of graphs. Do you think this is due to chance, or can you think of some reason why
v =
4 should be unique? If the table were continued, do you think more odd numbers would turn up in the second column?

28.
  
Prove that the graphs of
Figure 47
are isomorphic.

29.
  
Prove that the graphs of
Figure 48
are all isomorphic to the utility graph.

30–37
.
  
In each of
Figures 49-
56
, decide whether or not the two graphs are isomorphic. If you decide they are isomorphic, prove it by finding a labeling under which they would be equal. If you decide they are not isomorphic, prove it by finding a property which is preserved by isomorphism but in terms of which the two graphs differ. (We now have six such properties: the four mentioned in the text, and two more introduced in
Exercises 20
and
24
.)

38.
  
A chess tournament consists of twenty-five players, each of whom
plays one game with every other player. How many games are played during the tournament?

Figure 49

Figure 50

Figure 51

Figure 52

Figure 53

Figure 54

39.
  
When I said on page 56 “There is no simple way of determining the number of graphs having a given
v, ”
I meant of course that there is no simple way of determining the number of
nonisomorphic
graphs having a given
v.
Prove that there are exactly 2
^{(1/2)
v
(
v
−1)}
unequal graphs whose
v
vertices have been labeled with the integers from 1 to
v.

Figure 55

Figure 56

Figure 56A

40
.
  
The utility puzzle mentioned on page 27 was invented by Henry Ernest Dudeney (1857–1930), a self-taught mathematician who was
the foremost puzzlemaker of his time. Here is another of Dudeney's puzzles, one which, unlike the utility puzzle, has a solution. In
figure 56A
connect
a
to
A
,
b
to
B
,
c
to
C
and
d
to
D
by edges which are inside the rectangle and don't cross one another.

Suggested reading

On Sets

*
One, Two, Three ... Infinity: Facts and Speculations of Science
by George Gamow (Viking, 1961), chapter 1.

*
Stories About Sets
by N. Ya. Vilenkin (Academic Press, 1968), chapters 1–3.

On Paradoxes

*“Paradox Lost and Paradox Regained” by Edward Kasner and James R. Newman, reprinted in volume 3 of
The World of Mathematics
, edited by James R. Newman (Simon and Schuster, 1956).

*“Paradox” by W. V. Quine in the April, 1962 issue of
Scientific American
; reprinted as chapter 28 of
Mathematics in the Modern World: Readings from Scientific American
with introductions by Morris Kline (W. H. Freeman, 1968).

On Bertrand Russell

“Bertrand Russell 1872–1970” in the February 16, 1970 issue of
Newsweek.
A zippy obituary.

On Logic

*“What the Tortoise Said to Achilles” by Lewis Carroll, reprinted in volume 4 of
The World of Mathematics
, edited by James R. Newman (Simon and Schuster, 1956).

On Mathematical Discovery

*
How to Solve It: A New Aspect of Mathematical Method
by G. Polya (Princeton University Press, 1957). Handy when you're stuck.

3. PLANAR GRAPHS

Introduction

Definition 18
.
A graph is
planar
if it is isomorphic to a graph that has been drawn in a plane without edge-crossings. Otherwise a graph is
nonplanar
.

(I have dropped the distinction between an abstractly given graph and a graph diagram. I use the word “graph” to refer to both. When I say “a graph that has been drawn, etc.,” I obviously mean a graph diagram.)

Thus a planar graph, when drawn on a flat surface, either has no edge-crossings or can be redrawn without them. The three graphs of
Figure 57
are planar, the first two because they have no edge-crossings and the third because its edge-crossing is avoidable—the third is isomorphic to the second.

In principle it is a simple matter to demonstrate planarity. Like isomorphism, planarity is a potential. A graph is planar if a certain task, the drawing of the graph without edge-crossings, is possible; and we can show the task to be possible simply by performing it. In practice this is not always easy. For example, although the graph of
Figure 58a
is planar, you might require several tries in order to draw it without edge-crossings.