Introduction to Graph Theory (45 page)

Chapter 8. Euler Walks and Hamilton Walks

4
.
  
On the chessboard, from each of the two squares abutting each corner square, a knight has exactly three moves, so
C
has eight vertices of degree 3 and therefore, by
Theorems 30
and
31
, no euler walks.

11
.
  
Create a multigraph
M
(
G
) by adding
n
edges, each joining two odd vertices.
M
(
G
) has a closed euler walk by
Theorem 34
. Removing the
n
edges from the euler walk of
M
(
G
) breaks it into
n
open walks in
G
, each of which begins and ends at an odd vertex and which, together, use every edge of
G
exactly once.

14
.
  
Each vertex of
L
(
G
) corresponds to an edge of
G
which, by
Theorem 30
, has an even degree at each end, that is, is incident to an odd number of other edges at each end and so is incident to an even number of edges in all; thus the degree of every vertex in
L
(
G
) is even.
L
(
G
) is also connected, so
L
(
G
) has a closed euler walk by
Theorem 30
.

Let “
E
₁
” be the first edge in
G
's closed euler walk, “
E
₂
” be the second edge, and so on, so that the closed euler walk can be represented in terms of its edges as
E
₁
E
₂
. . .
E
_e
. Then this identical expression, considered as an arrangement of the vertices of
L
(
G
), is an open hamilton walk in
L
(
G
). Since the euler walk in
G
was closed, the terminal vertex of edge E
_e
in
G
is identical to the initial vertex of edge
E
₁
meaning that
E
_e
and
E
_1,
as edges of
G
, are incident and so, as vertices of
L
(
G
), are adjacent. Thus the above open hamilton walk in
L
(
G
) can be extended to a closed hamilton walk,
E
₁
E
₂
. . .
E
_e
E
₁
.

20
.
  
Consider one particular vertex of
G
, say of degree “
d
,” and consider one particular edge incident to that vertex. At that vertex, that edge is incident to
d
− 1 other edges, contributing
d
− 1 to the degree-total over in
L
(
G
). But at that same vertex, each of the other incident edges also has
d
− 1 incidences, so in all the incidences at our particular vertex contribute
d
(
d
− 1) to the degree-total in
L
(
G
). Thus the degrees in
L
(
G
) add up to

Multiply this out, and use
Exercise 11
, p. 57, twice.

INDEX

adjacent edges,
20

adjacent vertices,
20

algebra,
109–111

algebraic topology,
108–111

analytic geometry,
110

applied mathematics vs. pure mathematics,
ix
,
1–9

Archimedes,
9

Aristotle,
4
,
8

“Around the World,”
177

Bell's
Men of Mathematics
,
7

bridge,
115

Brown's
Laws of Form
,
8

c
, see connectivity

C
₃
,
116
;

see also
K
₃

C
₄
,
116

Catherine the Great,
97

chromatic number,
128–129
;

of complements,
139–140
;

of planar graphs,
130–131
;

of the surface
S
_n
,
164–168

coloring, of faces,
136–139
;

of vertices,
127–136
;

see also chromatic number complement
31–32
(see also
47–49
);

chromatic number of,
139–140
;

number of edges of,
57
;

preserved by isomorphism,
59
;

self-complementary graphs,
57

complete graphs
26–27
(see also
47–49
);

as connected,
98
;

complements of,
31
;

genus of,
154
;

nonplanarity of
K
_v
for
v
≥ 6,
73
;

number of edges before first crossing,
170
;

number of edges of,
27–30
;

regularity of,
117
;

relation to “
L
” and “
U
”,
168
;

walks in,
97
;

see also
K
₁
,
K
₃
,
K
₄
,
K
₅
,
K
₆
,
K
₇
.

component,
113
,
115
,
173
;

see also “pieces” of a graph

connected graphs,
97–98
,
123
,
148–154
,
156–164
,
168
,
173–176
,
178
,
193
;

see also planar and connected graphs connected multigraphs,
183–185

connectivity,
114–116
,
191

continuous deformation,
108–109
,
145

continuous simple closed curve,
66–68
,
108–109

convert-solve-reconvert,
110–111
,
184

crossing number,
170

Császár polyhedron,
169

cube,
120–123
,
125
,
127–128

C
_v
, see cyclic graphs cyclic graphs,
25–26
(see also
47–49
);

and hamilton walks,
191
;

and polygonal graphs,
115–116
;

and Two Color Theorem,
139
;

as connected,
98
;

as expansions of
K
₃
,
93
;

as only connected graphs regular of degree 2,
123
;

as platonic,
118
;

as regular polygons,
121
;

complements of,
31
;

genus of,
144
;

line graphs of,
193
;

regularity of,
117
;

self-complementary,
57

degree of a vertex,
41
;

distribution of degrees,
41–47
;

in a multigraph,
184
;

sum of degrees,
57
;

sum of degrees in a multigraph,
187

Descartes, René,
110

diagrams,
20–24

digraphs,
24

directed graphs,
24

disconnected graphs,
97–98
,
108
,
173

disconnected multigraphs,
183

distribution of degrees,
41–47

distribution of subgraphs,
57–59

dodecahedron,
120–123
,
177

dual graphs,
124–125
;

and coloring,
137–138

Dudeney, Henry Ernest,
62–63

e
,
19

edge,
19

edge-crossings,
24
,
64
;

see also crossing number, genus, nonplanar graphs, planar graphs

edge set,
19

Einstein, Albert,
7

The Elements
,
2–6
,
123

element,
13

empty set,
14

equality, of graphs,
21
;

of graph diagrams,
21
;

of sets,
14

Euclid,
2–6
,
123

Euclidian geometry,
ix
,
1–6
,
108
,
121–123

Euler, Leonhard,
97
,
185–188

Euler's Formula (Euler's First Formula),
97
,
100–104
,
113
;

consequences of,
104–108
,
117
,
119
,
131–136
;

generalization of,
113
;

partial converse of,
113

Euler's Second Formula,
148–153
,
168
;

consequences of,
153–156
,
158–162
,
166–167

euler walk,
172–178
,
182
,
192–193
;

in a multigraph,
183–188

even vertex,
173
,
175
,
188
;

in a multigraph,
184

Excluded Middle. Law of,
18
,
56
,
98

expansions,
76–80
,
93–94
;

of
K
₃
,
93
;

of
K
₅
,
80
,
94
,
116
;

of supergraphs of
UG
or
K
₅
,
82–83
,
94
;

of
UG
,
80
,
94
,
116
;

supergraphs of expansions of
UG
or
K
₅
,
80–85
;

trisection graphs,
192–193

f
,
99
,
148

face,
99
,
147–148

Five Color Theorem,
130–136
,
165

Four Color Conjecture,
130–131
,
140
,
165
,
167–168

g
, see genus

Gardner, Martin,
169–170

genus,
141–170

geometry,
ix
,
1–6
,
108
,
121–123

g-platonic graphs,
158–164
;
168–170
;

see also platonic graphs graphs,
ix
,
9–10
,
19
;

number of (nonisomorphic),
50–56
;

number of unequal,
61–62
;

see also complement, complete graphs, connected graphs, cyclic graphs, disconnected graphs, dual graphs, expansions, g-platonic graphs, graph diagrams, line graphs, maps, nonplanar graphs, null graphs, path graphs, planar graphs, platonic graphs, polygonal graphs, regular graphs, subgraphs, supergraphs, utility graph, wheel graphs

graph diagrams,
20–24

Hamilton, William Rowan,
177

hamilton walk,
172
,
177–182
,
190–193

Harary's
Graph Theory
,
x
,
84
,
147
,
156
,
166

Hardy's
A Mathematician's Apology
,
38

Heawood Coloring Theorem,
164–168

Heawood, P. J.,
130
,
154–156
,
166

hexahedron, see cube

Hippasus,
16

icosahedron,
120–123
,
135–136

incidence,
20

induction, mathematical,
101–104
,
111–112
,
131–136

Intuitionist mathematicians,
18

is, meaning “is isomorphic to”,
47–50

isolated vertex,
20

isomorphism,
33–49
;

alternate definition of,
38
;

as criterion whereby graphs are judged ‘‘the same”,
47–50
;

definition,
35
;

how to recognize,
39–47
;

properties preserved by,
41–47
,
57–59
,
94
;

transitivity of,
94

Jeans, Sir James,
7

Jordan, Camille,
66
,
68

Jordan Curve Theorem,
66
,
84
,
99
,
109
,
111

k
, see crossing number