A First Course in Graph Theory and Combinatorics: Second Edition (Texts and Readings in Mathematics, 55)

Preface to Second Edition
Preface to First Edition
Contents
About the Authors
1 Basic Graph Theory
	1.1 Königsberg Bridges Problem
	1.2 What Is a Graph?
	1.3 Mathematical Induction
	1.4 Eulerian Graphs
	1.5 Bipartite Graphs
	1.6 Exercises
	Exercises
2 Basic Counting
	2.1 Finite Sets and Permutations
	2.2 Fibonacci Numbers
	2.3 Catalan Numbers
	2.4 Derangements and Involutions
	2.5 Bell Numbers
	2.6 Exercises
	Exercises
	References
3 The Principle of Inclusion and Exclusion
	3.1 The Main Theorem
	3.2 Derangements Revisited
	3.3 Counting Surjective Maps
	3.4 Stirling Numbers of the First Kind
	3.5 Stirling Numbers of the Second Kind
	3.6 Exercises
	Exercises
4 Graphs and Matrices
	4.1 Adjacency Matrix
	4.2 Graph Isomorphisms
	4.3 Bipartite Graphs and Eigenvalues
	4.4 Diameters and Eigenvalues
	4.5 Incidence Matrices and the Laplacian Matrix
	4.6 Exercises
	Exercises
5 Trees
	5.1 Forests, Trees, and Leaves
	5.2 Labelled Trees
	5.3 Spanning Trees
	5.4 MST, BFS, and DFS
	5.5 Lagrange's Inversion Formula
	5.6 Exercises
	Exercises
	Reference
6 Möbius Inversion and Graph Colouring
	6.1 Posets and Möbius Functions
	6.2 Applications of Möbius Inversion
	6.3 The Chromatic Polynomial
	6.4 The Chromatic Number
	6.5 Sudoku Puzzles
	6.6 Exercises
	Exercises
	Reference
7 Enumeration Under Group Action
	7.1 Basic Facts About Groups
	7.2 The Orbit-Stabilizer Formula
	7.3 Burnside's Lemma
	7.4 Sylow Theorems
	7.5 Pólya Theory
	7.6 Exercises
	Exercises
	References
8 Matching Theory
	8.1 The Marriage Theorem
	8.2 Latin Squares
	8.3 Doubly Stochastic Matrices
	8.4 Weighted Bipartite Matching
	8.5 Matchings and Connectivity
	8.6 Exercises
	Exercises
	References
9 Block Designs
	9.1 Gaussian Binomial Coefficients
	9.2 Design Theory
	9.3 Incidence Matrices
	9.4 Bruck-Ryser-Chowla Theorem
	9.5 Codes and Designs
	9.6 Exercises
	Exercises
	Reference
10 Planar Graphs
	10.1 Euler's Formula
	10.2 The Platonic Solids
	10.3 The Five Colour Theorem
	10.4 Colouring Graphs on Surfaces
	10.5 Pick's Theorem
	10.6 Exercises
	Exercises
	References
11 Edges and Cycles
	11.1 Edge Colourings
	11.2 Hamiltonian Cycles
	11.3 Turán's Theorem
	11.4 Ramsey Theory
	11.5 Graham-Pollak Theorem
	11.6 Exercises
	Exercises
	References
12 Expanders and Ramanujan Graphs
	12.1 Eigenvalues and Expanders
	12.2 The Alon-Boppana Theorem
	12.3 Group Characters and Cayley Graphs
	12.4 The Ihara Zeta Function of a Graph
	12.5 Ramanujan Graphs
	12.6 Exercises
	References
13 Hints
Appendix  Index
Index