Introduction to Graph Theory (27 page)

Figure 109

It is apparent from
Figure 109
that to each row of the table there corresponds at least one platonic graph. Though not apparent it is also true that to each row of the table there corresponds
only
the one platonic graph named in the last column. This requires proof.

In principle we could construct such a proof as follows. For each row of the table, we could look at the numbers in the “
v
” and “
e
” columns, draw all graphs having that number of vertices and that number of edges, and check that the one named in the last column is the only one that is platonic. In practice such a proof would be reasonable for only the first and fourth rows of the table (see
Exercise 3
). The next simplest row is the second, and there are 1, 312 graphs with eight vertices and twelve edges! As you might expect therefore, there are shorter ways of proving that the graphs of
Figure 109
are the only platonic graphs corresponding to the table, but we shall pass them over.

Figure 110

History

In the terminology of geometry a “regular polygon” is a polygon—a closed plane figure bounded by a finite number of straight lines—having all its sides the same length and all its angles the same size. There are infinitely many regular polygons, the first four of which are drawn in
Figure 110
. Considered as a graph, a regular polygon with
v
sides is isomorphic to the cyclic graph
C
_v
.

Still in the terminology of geometry, a
regular polyhedron
is apolyhedron—a closed solid figure bounded by a finite number of planes—having congruent regular polygons for its faces and all of its corner angles the same size. A cube is a regular polyhedron.

The notion “regular polyhedron” is an extension to three dimensions of the notion “regular polygon”. In cases like this mathematical experience suggests that since there are infinitely many regular polygons, there are probably infinitely many regular polyhedra as well.

The Pythagoreans (about 500 B.C.) seem to have been the first to discover, if not to prove, the surprising fact that contrary to expectations, there are only five regular polyhedra: the regular tetrahedron, the regular hexahedron (or “cube”), the regular octahedron, the regular dodecahedron, and the regular icosahedron. (“Hedron” means “face”; the prefixes mean respectively “four”, “six”, “eight”, “twelve”, and “twenty”.)

The five regular polyhedra have been drawn in
Figure 111
. Considered as three-dimensional drawings of graphs, they are isomorphic to the graphs of
Figure 109
. Thus, except for
K
₁
which is platonic in only a trivial sense, every platonic graph corresponds to either a regular polygon or a regular polyhedron.

Figure 111

The Pythagoreans were mystics, and believed that the tetrahedron, cube, octahedron, and icosahedron respectively underlay the structure of the four elements of Greek science: fire, earth, air, and water. The dodecahedron they identified with the universe as a whole. Plato was quite taken by all this and spent some time in his dialogue
Timaeus
(named after the Pythagorean who is the chief interlocutor) discussing the connection between the five regular polyhedra and the structure of the universe. For this reason the regular polyhedra came to be known as the “platonic solids”.

The final book of Euclid's
Elements
is devoted to the five regular polyhedra. Some scholars argue that this analysis was Euclid's goal in composing the
Elements
.

Johannes Kepler (1571–1630), a German astronomer-astrologer contemporary with Shakespeare, discoverer of three laws of planetary motion that still bear his name, was seduced at an early age by Pythagorean mysticism. So strong was his faith in the mathematical harmony of the universe that he quickly became convinced of a relationship between the five regular polyhedra and the six known planets. At that time planetary orbits were thought to be circular, and Kepler imagined the circles as equators of huge spheres. He found that if a cube were inscribed in the sphere of Saturn, and another sphere inscribed in the cube, the second sphere would be the sphere of Jupiter; that if a regular tetrahedron were inscribed in the sphere of Jupiter, and a sphere inscribed in the tetrahedron, this third sphere would be the sphere of Mars; and so on down the line, with the five regular polyhedra nesting perfectly among the spheres of the six planets. Kepler concluded that the five regular polyhedra accounted for both the number of planets—there could be only six—and their spacing in the solar system. When his own later work revealed that (1) the spacing of the planetary orbits did not correspond to the nesting of the polyhedra as accurately as he had thought, and (2) planetary orbits are not circular but elliptical, Kepler was forced to put aside his beliefs about the regular polyhedra, but only after great mental anguish.

Exercises

  
1.
  
Draw all connected graphs that are regular of degree 1.

2.
  
Satisfy yourself that every connected graph which is regular of degree 2 is a cyclic graph. Show by example that deleting the word “connected” results in a false statement.

3.
  
It's easy to see that
K
₄
is the only platonic graph corresponding to the first row of the table on page 121, as
K
₄
is the only graph having
v
= 4 and
e
= 6 (see
Figure 45
). Now verify that there is only one platonic graph corresponding to the fourth row by drawing all graphs with
v
= 6 and
e
= 12 (there are five of them) and checking that only the octahedron is platonic.

4
.
  
Prove: there is no regular graph with
v
= 6 and
e
= 10. (This can be done algebraically, without drawing a single graph.)

5.
  
Prove: if a graph has an odd number of vertices and is regular of degree
d
, then
d
must be even.

6
.
  
Find a graph other than the cube that has
v
= 8 and is regular of degree 3.

7.
  
Draw all regular graphs with six vertices or less. There are twenty of them
.

8.
  
Definition
. A
dual graph
of a planar graph is formed by taking a crossing-free plane drawing of the planar graph, placing a dot inside each face, and joining two dots whenever the borders of the corresponding faces have one or more edges in common.

Example
. The planar graph of
Figure 112a
has been redrawn in
112b
along with a dual; the dual is drawn by itself in
112c
.

Figure 112

Note that only a planar graph can have a dual, and that a dual is always planar and connected. But a dual is not always unique: some planar graphs have several different duals, each arising from a different crossing-free plane drawing. This is why in the definition I said “a” dual instead of “the” dual.

Example
.
Figure 113a
is isomorphic to
Figure 112a
, yet the dual formed in 113b and shown by itself in 113c is not isomorphic to the dual of
Figure 112c
.

Each of the platonic graphs does, however, have a unique dual. For example,
K
₁
has only one dual, itself, and each cyclic graph has only one dual,
K
₂
. The octahedron and its unique dual are shown in the three-dimensional drawing of
Figure 114
. Draw the duals of the other four platonic graphs. Your results will help explain the curious symmetry of the table on page 121.

9.
  
Prove that every wheel graph
W
_v
(see Chapter 2,
Exercise 6
) is isomorphic to its (unique) dual.

Figure 113