Collected Works: Volume I: Publications 1929-1936

Cover......Page 1
Title......Page 4
Copyright Page......Page 5
Preface......Page 8
Contents......Page 13
1.1 Graphs......Page 22
1.2 Subgraphs......Page 24
1.3 Automorphisms......Page 25
1.4 Homomorphisms......Page 27
1.5 Circulant Graphs......Page 29
1.6 Johnson Graphs......Page 30
1.7 Line Graphs......Page 31
1.8 Planar Graphs......Page 33
Exercises......Page 37
Notes......Page 38
References......Page 39
2.1 Permutation Groups......Page 40
2.2 Counting......Page 41
2.3 Asymmetric Graphs......Page 43
2.4 Orbits on Pairs......Page 46
2.5 Primitivity......Page 48
2.6 Primitivity and Connectivity......Page 50
Exercises......Page 51
References......Page 53
3.1 Vertex-Transitive Graphs......Page 54
3.2 Edge-Transitive Graphs......Page 56
3.3 Edge Connectivity......Page 58
3.4 Vertex Connectivity......Page 60
3.5 Matchings......Page 64
3.6 Hamilton Paths and Cycles......Page 66
3.7 Cayley Graphs......Page 68
3.8 Directed Cayley Graphs with No Hamilton Cycles......Page 70
3.9 Retracts......Page 72
3.10 Transpositions......Page 73
Exercises......Page 75
Notes......Page 77
References......Page 78
4.1 Arc-Transitive Graphs......Page 80
4.2 Arc Graphs......Page 82
4.3 Cubic Arc-Transitive Graphs......Page 84
4.4 The Petersen Graph......Page 85
4.5 Distance-Transitive Graphs......Page 87
4.6 The Coxeter Graph......Page 90
4.7 Tutte\'s 8-Cage......Page 92
Exercises......Page 95
References......Page 97
5. Generalized Polygons and Moore Graphs......Page 98
5.1 Incidence Graphs......Page 99
5.2 Projective Planes......Page 100
5.3 A Family of Projective Planes......Page 101
5.4 Generalized Quadrangles......Page 102
5.5 A Family of Generalized Quadrangles......Page 104
5.6 Generalized Polygons......Page 105
5.7 Two Generalized Hexagons......Page 109
5.8 Moore Graphs......Page 111
5.9 The Hoffman-Singleton Graph......Page 113
5.10 Designs......Page 115
Exercises......Page 118
References......Page 121
6.1 The Basics......Page 124
6.2 Cores......Page 125
6.3 Products......Page 127
6.4 The Map Graph......Page 129
6.5 Counting Homomorphisms......Page 130
6.6 Products and Colourings......Page 131
6.7 Uniquely Colourable Graphs......Page 134
6.8 Foldings and Covers......Page 135
6.9 Cores with No Triangles......Page 137
6.10 The Andrasfai Graphs......Page 139
6.11 Colouring Andrasfai Graphs......Page 140
6.12 A Characterization......Page 142
6.13 Cores of Vertex-\'fransitive Graphs......Page 144
6.14 Cores of Cubic Vertex-Transitive Graphs......Page 146
Exercises......Page 149
Notes......Page 153
References......Page 154
7.1 Fractional Colourings and Cliques......Page 156
7.2 Fractional Cliques......Page 157
7.3 Fractional Chromatic Number......Page 158
7.4 Homomorphisms and Fractional Colourings......Page 159
7.5 Duality......Page 162
7.6 Imperfect Graphs......Page 163
7.7 Cyclic Interval Graphs......Page 166
7.8 Erdos-Ko-Rado......Page 167
7.9 Homomorphisms of Kneser Graphs......Page 169
7.10 Induced Homomorphisms......Page 170
7.11 The Chromatic Number of the Kneser Graph......Page 171
7.12 Gale\'s Theorem......Page 173
7.13 Welzl\'s Theorem......Page 174
7.14 The Cartesian Product......Page 175
7.15 Strong Products and Colourings......Page 176
Exercises......Page 177
Notes......Page 180
References......Page 181
8.1 The Adjacency Matrix......Page 184
8.2 The Incidence Matrix......Page 186
8.3 The Incidence Matrix of an Oriented Graph......Page 188
8.4 Symmetric Matrices......Page 190
8.5 Eigenvectors......Page 192
8.6 Positive Semidefinite Matrices......Page 194
8.7 Subharmonic Functions......Page 196
8.8 The Perron-Frobenius Theorem......Page 199
8.9 The Rank of a Symmetric Matrix......Page 200
8.10 The Binary Rank of the Adjacency Matrix......Page 202
8.11 The Symplectic Graphs......Page 204
8.12 Spectral Decomposition......Page 206
8.13 Rational Functions......Page 208
Exercises......Page 209
References......Page 213
9.1 Interlacing......Page 214
9.3 Equitable Partitions......Page 216
9.4 Eigenvalues of Kneser Graphs......Page 220
9.5 More Interlacing......Page 223
9.6 More Applications......Page 224
9.7 Bipartite Subgraphs......Page 227
9.8 Fullerenes......Page 229
9.9 Stability of Fullerenes......Page 231
Exercises......Page 234
Notes......Page 236
References......Page 237
10. Strongly Regular Graphs......Page 238
10.1 Parameters......Page 239
10.2 Eigenvalues......Page 240
10.3 Some Characterizations......Page 242
10.4 Latin Square Graphs......Page 244
10.5 Small Strongly Regular Graphs......Page 247
10.6 Local Eigenvalues......Page 248
10.7 The Krein Bounds......Page 252
10.8 Generalized Quadrangles......Page 256
10.9 Lines of Size Three......Page 258
10.10 Quasi-Symmetric Designs......Page 260
10.11 The Witt Design on 23 Points......Page 262
10.12 The Symplectic Graphs......Page 263
Exercises......Page 265
Notes......Page 267
References......Page 268
11.1 Equiangular Lines......Page 270
11.2 The Absolute Bound......Page 272
11.3 Tightness......Page 273
11.4 The Relative Bound......Page 274
11.5 Switching......Page 275
11.6 Regular Two-Graphs......Page 277
11.7 Switching and Strongly Regular Graphs......Page 279
11.8 The Two-Graph on 276 Vertices......Page 281
Exercises......Page 283
References......Page 284
12.1 Generalized Line Graphs......Page 286
12.2 Star-Closed Sets of Lines......Page 287
12.3 Reflections......Page 288
12.4 Indecomposable Star-Closed Sets......Page 289
12.5 A Generating Set......Page 291
12.6 The Classification......Page 292
12.7 Root Systems......Page 293
12.8 Consequences......Page 295
12.9 A Strongly Regular Graph......Page 297
Exercises......Page 298
References......Page 299
13.1 The Laplacian Matrix......Page 300
13.2 Trees......Page 302
13.3 Representations......Page 305
13.4 Energy and Eigenvalues......Page 308
13.5 Connectivity......Page 309
13.6 Interlacing......Page 311
13.7 Conductance and Cutsets......Page 313
13.8 How to Draw a Graph......Page 314
13.9 The Generalized Laplacian......Page 316
13.10 Multiplicities......Page 319
13.11 Embeddings......Page 321
Exercises......Page 323
Notes......Page 326
References......Page 327
14. Cuts and Flows......Page 328
14.1 The Cut Space......Page 329
14.2 The Flow Space......Page 331
14.3 Planar Graphs......Page 333
14.4 Bases and Ear Decompositions......Page 334
14.5 Lattices......Page 336
14.6 Duality......Page 337
14.7 Integer Cuts and Flows......Page 338
14.8 Projections and Duals......Page 340
14.9 Chip Firing......Page 342
14.10 Two Bounds......Page 344
14.11 Recurrent States......Page 346
14.12 Critical States......Page 347
14.13 The Critical Group......Page 348
14.14 Voronoi Polyhedra......Page 350
14.15 Bicycles......Page 353
14.16 The Principal Tripartition......Page 355
Exercises......Page 357
References......Page 359
15.1 Rank Functions......Page 362
15.2 Matroids......Page 364
15.3 Duality......Page 365
15.4 Restriction and Contraction......Page 367
15.5 Codes......Page 368
15.6 The Deletion-Contraction Algorithm......Page 370
15.7 Bicycles in Binary Codes......Page 372
15.8 Two Graph Polynomials......Page 374
15.9 Rank Polynomial......Page 376
15.10 Evaluations of the Rank Polynomial......Page 378
15.11 The Weight Enumerator of a Code......Page 379
15.12 Colourings and Codes......Page 380
15.13 Signed Matroids......Page 382
15.14 Rotors......Page 384
15.15 Submodular Functions......Page 387
Exercises......Page 390
Notes......Page 392
References......Page 393
16 Knots......Page 394
16.1 Knots and Their Projections......Page 395
16.2 Reidemeister Moves......Page 397
16.3 Signed Plane Graphs......Page 400
16.4 Reidemeister moves on graphs......Page 402
16.5 Reidemeister Invariants......Page 404
16.6 The Kauffman Bracket......Page 406
16.7 The Jones Polynomial......Page 407
16.8 Connectivity......Page 409
Exercises......Page 412
References......Page 413
17.1 Eulerian Partitions and Tours......Page 416
17.2 The Medial Graph......Page 419
17.3 Link Components and Bicycles......Page 421
17.4 Gauss Codes......Page 424
17.5 Chords and Circles......Page 426
17.6 Flipping Words......Page 428
17.7 Characterizing Gauss Codes......Page 429
17.8 Bent Tours and Spanning Trees......Page 431
17.9 Bent Partitions and the Rank Polynomial......Page 434
17.10 Maps......Page 435
17.11 Orientable Maps......Page 438
17.12 Seifert Circles......Page 440
17.13 Seifert Circles and Rank......Page 441
Exercises......Page 444
Notes......Page 445
References......Page 446
Glossary of Symbols......Page 448
Index......Page 454