Graph Theory

Preface

1: The Basics
1.1 Graphs*
1.2 The degree of a vertex*
1.3 Paths and cycles*
1.4 Connectivity*
1.5 Trees and forests*
1.6 Bipartite graphs*
1 7 Contraction and minors*
1.8 Euler tours*
1.9 Some linear algebra
1.10 Other notions of graphs
Exercises
Notes

2: Matching, Covering and Packing
2.1 Matching in bipartite graphs*
2.2 Matching in general graphs(*)
2.3 Packing and covering
2.4 Tree-packing and arboricity
2.5 Path covers
Exercises
Notes

3: Connectivity
3.1 2-Connected graphs and subgraphs*
3.2 The structure of 3-connected graphs(*)
3.3 Menger's theorem*
3.4 Mader's theorem
3.5 Linking pairs of vertices(*)
Exercises
Notes

4: Planar Graphs
4.1 Topological prerequisites*
4.2 Plane graphs*
4.3 Drawings
4.4 Planar graphs: Kuratowski's theorem*
4.5 Algebraic planarity criteria
4.6 Plane duality
Exercises
Notes

5: Colouring
5.1 Colouring maps and planar graphs*
5.2 Colouring vertices*
5.3 Colouring edges*
5.4 List colouring
5.5 Perfect graphs
Exercises
Notes

6: Flows
6.1 Circulations(*)
6.2 Flows in networks*
6.3 Group-valued flows
6.4 k-Flows for small k
6.5 Flow-colouring duality
6.6 Tutte's flow conjectures
Exercises
Notes

7: Extremal Graph Theory
7.1 Subgraphs*
7.2 Minors(*)
7.3 Hadwiger's conjecture*
7.4 Szemerédi's regularity lemma
7.5 Applying the regularity lemma
Exercises
Notes

8: Infinite Graphs
8.1 Basic notions, facts and techniques*
8.2 Paths, trees, and ends(*)
8.3 Homogeneous and universal graphs*
8.4 Connectivity and matching
8.5 The topological end space
Exercises
Notes

9: Ramsey Theory for Graphs
9.1 Ramsey's original theorems*
9.2 Ramsey numbers(*)
9.3 Induced Ramsey theorems
9.4 Ramsey properties and connectivity(*)
Exercises
Notes

10: Hamilton Cycles
10.1 Simple sufficient conditions*
10.2 Hamilton cycles and degree sequences*
10.3 Hamilton cycles in the square of a graph
Exercises
Notes

11: Random Graphs
11.1 The notion of a random graph*
11.2 The probabilistic method*
11.3 Properties of almost all graphs*
1 1.4 Threshold functions and second moments
Exercises
Notes

12: Minors, Trees and WQO
12.1 Well-quasi-ordering*
12.2 The graph minor theorem for trees*
12.3 Tree-decompositions
12.4 Tree-width and forbidden minors
12.5 The graph minor theorem(*)
Exercises
Notes

A. Infinite sets

B. Surfaces

Hints for all the exercises
Index
Symbol index

* Sections marked by an asterisk are recommended for a first course. Of sections marked (*), the beginning is recommended for a first course.