Preface
Contents
1 Symbolic Enumeration
1.1 Formal Power Series
1.2 Combinatorial Classes
1.3 Examples
1.4 Rooted Plane Trees
1.5 Lagrange Inversion Formula
1.6 Notes and References
1.7 Exercises
2 Labelled Enumeration
2.1 Exponential Generating Functions
2.2 Labelled Classes
2.3 Labelled Constructions
2.4 Permutations
2.5 Set Partitions
2.6 Words
2.7 Labelled Trees
2.8 Notes and References
2.9 Exercises
3 Enumeration with Symmetries
3.1 Group Actions
3.2 Group Action on Functions
3.3 The Cycle-Index Polynomial
3.4 The Rotations of the Cube
3.5 The Number of Non-Isomorphic Graphs
3.6 General Version of Polya's Theorem
3.7 Notes and References
3.8 Exercises
4 Finite Geometries and Latin Squares
4.1 Systems of Distinct Representatives
4.2 Latin Squares
4.3 Mutually Orthogonal Latin Squares
4.4 Linear Spaces
4.5 Projective Planes
4.6 Affine Planes
4.7 Projective Spaces
4.8 Notes and References
4.9 Exercises
5 Matchings
5.1 Kรถnig's Theorem
5.2 Hall's Marriage Theorem
5.3 Stable Matchings
5.4 Tutte's Theorem
5.5 Coverings and Independent Sets
5.6 Notes and References
5.7 Exercises
6 Connectivity
6.1 Vertex Connectivity
6.2 Structure of k-Connected Graphs for Small k
6.3 Menger's Theorem
6.4 Edge Connectivity
6.5 Notes and References
6.6 Exercises
7 Planarity
7.1 Plane Graphs
7.2 Kuratowski's Theorem
7.3 Wagner's Theorem
7.4 Whitney Theorem
7.5 Notes and References
7.6 Exercises
8 Graph Colouring
8.1 Vertex Colouring
8.2 Planar Graphs
8.3 Edge Colouring
8.4 List Colouring
8.5 Notes and References
8.6 Exercises
9 Extremal Graph Theory
9.1 Graphs Without Triangles
9.2 Graphs Without Complete Subgraphs
9.3 ErdลsโStone Theorem
9.4 Graphs Without Complete Bipartite Graphs
9.5 Graphs Without Even Cycles
9.6 Notes and References
9.7 Exercises
10 Hints and Solutions to Selected Exercises
References