A First Course in Graph Theory and Combinatorics

Contents

Chapter 1. Basic Notions of Graph Theory 1
1.1. The Königsberg Bridges Problem 1
1.2. What is a Graph? 2
1.3. Mathematical Induction and Graph Theory Proofs 4
1.4. Eulerian Graphs 6
1.5. Bipartite Graphs 7
1.6. Exercises 8

Chapter 2. Recurrence Relations 10
2.1. Binomial Coefficients 10
2.2. Derangements 13
2.3. Involutions 15
2.4. Fibonacci Numbers 16
2.5. Catalan Numbers 17
2.6. Bell Numbers 20
2.7. Exercises 21

Chapter 3. The Principle of Inclusion and Exclusion 24
3.1. The Main Theorem 24
3.2. Derangements Revisited 25
3.3. Counting Surjective Maps 25
3.4. Stirling Numbers of the First Kind 26
3.5. Stirling Numbers of the Second Kind 27
3.6. Exercises 30

Chapter 4. Matrices and Graphs 33
4.1. Adjacency and Incidence Matrices 33
4.2. Graph Isomorphism 34
4.3. Bipartite Graphs and Matrices 36
4.4. Diameter and Eigenvalues 37
4.5. Exercises 38

Chapter 5. Trees 41
5.1. Forests, Trees and Leaves 41
5.2. Counting Labeled Trees 42
5.3. Spanning Subgraphs 44
5.4. Minimllm Spanning Trees and Kruskal\'s Algorithm 47
5.5. Exercises 49

Chapter 6. Mobius Inversion and Graph Colouring 52
6.1. Posets and Mobius Functions 52
6.2. Lattices 54
6.3. The Classical Mobius Function 56
6.4. The Lattice of Partitions 57
6.5. Colouring Graphs 59
6.6. Colouring Trees and Cycles 62
6.7. Sharper Bounds for the Chromatic Number 64
6.8. Sudoku Puzzles and Chromatic Polynomials 66
6.9. Exercises 69

Chapter 7. Enumeration under Group Action 72
7.1. The Orbit-Stabilizer Formula 72
7.2. Burnside\'s Lemma 76
7.3. P6lya Theory 78
7.4. Exercises 84

Chapter 8. Matching Theory 86
8.1. The Marriage Theorem 86
8.2. Systems of Distinct Representatives 88
8.3. Systems of Common Representatives 89
8.4. Doubly Stochastic Matrices 90
8.5. Weighted Bipartite Matching 91
8.6. Matchings in General Graphs 94
8.7. Connectivity 95
8.8. Exercises 97

Chapter 9. Block Designs 100
9.1. Gaussian Binomial Coefficients 100
9.2. Introduction to Designs 103
9.3. Incidence Matrices 105
9.4. Examples of Designs 108
9.5. Proof of the Bruck-Ryser-Chowla Theorem 110
9.6. Codes and Designs 113
9.7. Exercises 115

Chapter 10. Planar Graphs 118
10.1. Euler\'s Formula 118
10.2. The Five Colour Theorem 121
10.3. Colouring Maps on Surfaces of Higher Genus 123
10.4. Exercises 125

Chapter 11. Edges and Cycles 127
11.1. Edge Colourings 127
11.2. Hamiltonian Cycles 130
11.3. Ramsey Theory 134
11.4. Exercises 139

Chapter 12. Regular Graphs 141
12.1. Eigenvalues of Regular Graphs 141
12.2. Diameter of Regular Graphs 142
12.3. Ramanujan Graphs 148
12.4. Basic Facts about Groups and Characters 148
12.5. Cayley Graphs 151
12.6. Expanders 154
12.7. Counting Paths in Regular Graphs 156
12.8. The Ihara Zeta Function of a Graph 157
12.9. Exercises 158

Chapter 13. Hints 160

Bibliography 169

Index 170