Contents

Preface
1 Graphs
1.1 Graphs . . . . . .
1.2 Subgraphs . . . .
1.3 Automorphisms .
1.4 Homomorphisms .
1.5 Circulant Graphs
1.6 Johnson Graphs .
1.7 Line Graphs . . .
1.8 Planar Graphs . .
Exercises . . . . . . . .
Notes . . . . . . . . . .
References . . . . . . . .

vii
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

1
1
3
4
6
8
9
10
12
16
17
18

2 Groups
2.1 Permutation Groups . . . .
2.2 Counting . . . . . . . . . . .
2.3 Asymmetric Graphs . . . . .
2.4 Orbits on Pairs . . . . . . .
2.5 Primitivity . . . . . . . . . .
2.6 Primitivity and Connectivity
Exercises . . . . . . . . . . . . . .
Notes . . . . . . . . . . . . . . . .
References . . . . . . . . . . . . . .

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

19
19
20
22
25
27
29
30
32
32

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

xiv

Contents

3 Transitive Graphs
3.1 Vertex-Transitive Graphs . . . . . . . . . . . . . .
3.2 Edge-Transitive Graphs . . . . . . . . . . . . . . .
3.3 Edge Connectivity . . . . . . . . . . . . . . . . . .
3.4 Vertex Connectivity . . . . . . . . . . . . . . . . .
3.5 Matchings . . . . . . . . . . . . . . . . . . . . . .
3.6 Hamilton Paths and Cycles . . . . . . . . . . . . .
3.7 Cayley Graphs . . . . . . . . . . . . . . . . . . . .
3.8 Directed Cayley Graphs with No Hamilton Cycles
3.9 Retracts . . . . . . . . . . . . . . . . . . . . . . .
3.10 Transpositions . . . . . . . . . . . . . . . . . . . .
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . .
Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . .
References . . . . . . . . . . . . . . . . . . . . . . . . . .

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

33
33
35
37
39
43
45
47
49
51
52
54
56
57

4 Arc-Transitive Graphs
4.1 Arc-Transitive Graphs . . .
4.2 Arc Graphs . . . . . . . . .
4.3 Cubic Arc-Transitive Graphs
4.4 The Petersen Graph . . . . .
4.5 Distance-Transitive Graphs .
4.6 The Coxeter Graph . . . . .
4.7 Tuttes 8-Cage . . . . . . . .
Exercises . . . . . . . . . . . . . .
Notes . . . . . . . . . . . . . . . .
References . . . . . . . . . . . . . .

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

59
59
61
63
64
66
69
71
74
76
76

5 Generalized Polygons and Moore Graphs

5.1 Incidence Graphs . . . . . . . . . . . . .
5.2 Projective Planes . . . . . . . . . . . . .
5.3 A Family of Projective Planes . . . . . .
5.4 Generalized Quadrangles . . . . . . . . .
5.5 A Family of Generalized Quadrangles . .
5.6 Generalized Polygons . . . . . . . . . . .
5.7 Two Generalized Hexagons . . . . . . . .
5.8 Moore Graphs . . . . . . . . . . . . . . .
5.9 The HomanSingleton Graph . . . . . .
5.10 Designs . . . . . . . . . . . . . . . . . . .
Exercises . . . . . . . . . . . . . . . . . . . . .
Notes . . . . . . . . . . . . . . . . . . . . . . .
References . . . . . . . . . . . . . . . . . . . . .

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

77
78
79
80
81
83
84
88
90
92
94
97
100
100

6 Homomorphisms
6.1 The Basics . . . . . . . . . . . . . . . . . . . . . . . . . .
6.2 Cores . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.3 Products . . . . . . . . . . . . . . . . . . . . . . . . . . .

103
103
104
106

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

Contents

6.4 The Map Graph . . . . . . . . . . . . . .

6.5 Counting Homomorphisms . . . . . . . .
6.6 Products and Colourings . . . . . . . . .
6.7 Uniquely Colourable Graphs . . . . . . .
6.8 Foldings and Covers . . . . . . . . . . . .
6.9 Cores with No Triangles . . . . . . . . .
6.10 The Andr
asfai Graphs . . . . . . . . . .
6.11 Colouring Andr
asfai Graphs . . . . . . .
6.12 A Characterization . . . . . . . . . . . .
6.13 Cores of Vertex-Transitive Graphs . . . .
6.14 Cores of Cubic Vertex-Transitive Graphs
Exercises . . . . . . . . . . . . . . . . . . . . .
Notes . . . . . . . . . . . . . . . . . . . . . . .
References . . . . . . . . . . . . . . . . . . . . .

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

xv

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

108
109
110
113
114
116
118
119
121
123
125
128
132
133

7 Kneser Graphs
7.1 Fractional Colourings and Cliques . . . . . . .
7.2 Fractional Cliques . . . . . . . . . . . . . . . .
7.3 Fractional Chromatic Number . . . . . . . . .
7.4 Homomorphisms and Fractional Colourings . .
7.5 Duality . . . . . . . . . . . . . . . . . . . . . .
7.6 Imperfect Graphs . . . . . . . . . . . . . . . .
7.7 Cyclic Interval Graphs . . . . . . . . . . . . .
7.8 Erd
osKoRado . . . . . . . . . . . . . . . . .
7.9 Homomorphisms of Kneser Graphs . . . . . .
7.10 Induced Homomorphisms . . . . . . . . . . . .
7.11 The Chromatic Number of the Kneser Graph
7.12 Gales Theorem . . . . . . . . . . . . . . . . .
7.13 Welzls Theorem . . . . . . . . . . . . . . . . .
7.14 The Cartesian Product . . . . . . . . . . . . .
7.15 Strong Products and Colourings . . . . . . . .
Exercises . . . . . . . . . . . . . . . . . . . . . . . .
Notes . . . . . . . . . . . . . . . . . . . . . . . . . .
References . . . . . . . . . . . . . . . . . . . . . . . .

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

135
135
136
137
138
141
142
145
146
148
149
150
152
153
154
155
156
159
160

8 Matrix Theory
8.1 The Adjacency Matrix . . . . . . . . . . . .
8.2 The Incidence Matrix . . . . . . . . . . . . .
8.3 The Incidence Matrix of an Oriented Graph
8.4 Symmetric Matrices . . . . . . . . . . . . . .
8.5 Eigenvectors . . . . . . . . . . . . . . . . . .
8.6 Positive Semidenite Matrices . . . . . . . .
8.7 Subharmonic Functions . . . . . . . . . . . .
8.8 The PerronFrobenius Theorem . . . . . . .
8.9 The Rank of a Symmetric Matrix . . . . . .
8.10 The Binary Rank of the Adjacency Matrix .

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

163
163
165
167
169
171
173
175
178
179
181

.
.
.
.
.
.
.
.
.
.

xvi

Contents

8.11 The Symplectic Graphs

8.12 Spectral Decomposition
8.13 Rational Functions . .
Exercises . . . . . . . . . . .
Notes . . . . . . . . . . . . .
References . . . . . . . . . . .

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

183
185
187
188
192
192

9 Interlacing
9.1 Interlacing . . . . . . . . . . . . . . . .
9.2 Inside and Outside the Petersen Graph
9.3 Equitable Partitions . . . . . . . . . . .
9.4 Eigenvalues of Kneser Graphs . . . . .
9.5 More Interlacing . . . . . . . . . . . . .
9.6 More Applications . . . . . . . . . . . .
9.7 Bipartite Subgraphs . . . . . . . . . . .
9.8 Fullerenes . . . . . . . . . . . . . . . .
9.9 Stability of Fullerenes . . . . . . . . . .
Exercises . . . . . . . . . . . . . . . . . . . .
Notes . . . . . . . . . . . . . . . . . . . . . .
References . . . . . . . . . . . . . . . . . . . .

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

193
193
195
195
199
202
203
206
208
210
213
215
216

10 Strongly Regular Graphs

10.1 Parameters . . . . . . . . . . . .
10.2 Eigenvalues . . . . . . . . . . .
10.3 Some Characterizations . . . . .
10.4 Latin Square Graphs . . . . . .
10.5 Small Strongly Regular Graphs
10.6 Local Eigenvalues . . . . . . . .
10.7 The Krein Bounds . . . . . . . .
10.8 Generalized Quadrangles . . . .
10.9 Lines of Size Three . . . . . . .
10.10 Quasi-Symmetric Designs . . . .
10.11 The Witt Design on 23 Points .
10.12 The Symplectic Graphs . . . . .
Exercises . . . . . . . . . . . . . . . .
Notes . . . . . . . . . . . . . . . . . .
References . . . . . . . . . . . . . . . .

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

217
218
219
221
223
226
227
231
235
237
239
241
242
244
246
247

. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
Regular Graphs

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

249
249
251
252
253
254
256
258

11 Two-Graphs
11.1 Equiangular Lines . . .
11.2 The Absolute Bound .
11.3 Tightness . . . . . . . .
11.4 The Relative Bound . .
11.5 Switching . . . . . . . .
11.6 Regular Two-Graphs .
11.7 Switching and Strongly

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

Contents

11.8 The
Exercises
Notes . .
References

Two-Graph
. . . . . . .
. . . . . . .
. . . . . . .

on 276
. . . .
. . . .
. . . .

Vertices
. . . . .
. . . . .
. . . . .

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

xvii

.
.
.
.

260
262
263
263

12 Line Graphs and Eigenvalues

12.1 Generalized Line Graphs . . . . .
12.2 Star-Closed Sets of Lines . . . . .
12.3 Reections . . . . . . . . . . . . .
12.4 Indecomposable Star-Closed Sets
12.5 A Generating Set . . . . . . . . .
12.6 The Classication . . . . . . . . .
12.7 Root Systems . . . . . . . . . . .
12.8 Consequences . . . . . . . . . . .
12.9 A Strongly Regular Graph . . . .
Exercises . . . . . . . . . . . . . . . . .
Notes . . . . . . . . . . . . . . . . . . .
References . . . . . . . . . . . . . . . . .

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

265
265
266
267
268
270
271
272
274
276
277
278
278

13 The Laplacian of a Graph

13.1 The Laplacian Matrix . . .
13.2 Trees . . . . . . . . . . . .
13.3 Representations . . . . . .
13.4 Energy and Eigenvalues . .
13.5 Connectivity . . . . . . . .
13.6 Interlacing . . . . . . . . .
13.7 Conductance and Cutsets .
13.8 How to Draw a Graph . .
13.9 The Generalized Laplacian
13.10 Multiplicities . . . . . . . .
13.11 Embeddings . . . . . . . .
Exercises . . . . . . . . . . . . .
Notes . . . . . . . . . . . . . . .
References . . . . . . . . . . . . .
14 Cuts
14.1
14.2
14.3
14.4
14.5
14.6
14.7
14.8
14.9
14.10

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

279
279
281
284
287
288
290
292
293
295
298
300
302
305
306

and Flows
The Cut Space . . . . . . . . .
The Flow Space . . . . . . . .
Planar Graphs . . . . . . . . .
Bases and Ear Decompositions
Lattices . . . . . . . . . . . . .
Duality . . . . . . . . . . . . .
Integer Cuts and Flows . . . .
Projections and Duals . . . .
Chip Firing . . . . . . . . . .
Two Bounds . . . . . . . . . .

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

307
308
310
312
313
315
316
317
319
321
323

.
.
.
.
.
.
.
.
.
.
.
.
.
.

xviii

Contents

14.11 Recurrent States . . . . . .

14.12 Critical States . . . . . . .
14.13 The Critical Group . . . .
14.14 Voronoi Polyhedra . . . . .
14.15 Bicycles . . . . . . . . . .
14.16 The Principal Tripartition
Exercises . . . . . . . . . . . . .
Notes . . . . . . . . . . . . . . .
References . . . . . . . . . . . . .

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

325
326
327
329
332
334
336
338
338

15 The Rank Polynomial

15.1 Rank Functions . . . . . . . . . . . .
15.2 Matroids . . . . . . . . . . . . . . . .
15.3 Duality . . . . . . . . . . . . . . . . .
15.4 Restriction and Contraction . . . . .
15.5 Codes . . . . . . . . . . . . . . . . . .
15.6 The DeletionContraction Algorithm
15.7 Bicycles in Binary Codes . . . . . . .
15.8 Two Graph Polynomials . . . . . . .
15.9 Rank Polynomial . . . . . . . . . . .
15.10 Evaluations of the Rank Polynomial .
15.11 The Weight Enumerator of a Code .
15.12 Colourings and Codes . . . . . . . . .
15.13 Signed Matroids . . . . . . . . . . . .
15.14 Rotors . . . . . . . . . . . . . . . . .
15.15 Submodular Functions . . . . . . . .
Exercises . . . . . . . . . . . . . . . . . . .
Notes . . . . . . . . . . . . . . . . . . . . .
References . . . . . . . . . . . . . . . . . . .

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

341
341
343
344
346
347
349
351
353
355
357
358
359
361
363
366
369
371
372

16 Knots
16.1 Knots and Their Projections .
16.2 Reidemeister Moves . . . . . .
16.3 Signed Plane Graphs . . . . .
16.4 Reidemeister moves on graphs
16.5 Reidemeister Invariants . . . .
16.6 The Kauman Bracket . . . .
16.7 The Jones Polynomial . . . .
16.8 Connectivity . . . . . . . . . .
Exercises . . . . . . . . . . . . . . .
Notes . . . . . . . . . . . . . . . . .
References . . . . . . . . . . . . . . .

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

373
374
376
379
381
383
385
386
388
391
392
392

17 Knots and Eulerian Cycles

17.1 Eulerian Partitions and Tours . . . . . . . . . . . . . . .
17.2 The Medial Graph . . . . . . . . . . . . . . . . . . . . .

395
395
398

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

17.3 Link Components and Bicycles . . . . . . .

17.4 Gauss Codes . . . . . . . . . . . . . . . . .
17.5 Chords and Circles . . . . . . . . . . . . .
17.6 Flipping Words . . . . . . . . . . . . . . .
17.7 Characterizing Gauss Codes . . . . . . . .
17.8 Bent Tours and Spanning Trees . . . . . .
17.9 Bent Partitions and the Rank Polynomial
17.10 Maps . . . . . . . . . . . . . . . . . . . . .
17.11 Orientable Maps . . . . . . . . . . . . . . .
17.12 Seifert Circles . . . . . . . . . . . . . . . .
17.13 Seifert Circles and Rank . . . . . . . . . .
Exercises . . . . . . . . . . . . . . . . . . . . . .
Notes . . . . . . . . . . . . . . . . . . . . . . . .
References . . . . . . . . . . . . . . . . . . . . . .

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

Contents

xix

.
.
.
.
.
.
.
.
.
.
.
.
.
.

400
403
405
407
408
410
413
414
417
419
420
423
424
425

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

Glossary of Symbols

427

Index

433

http://www.springer.com/978-0-387-95241-3