Introduction 1
1 Definitions and examples 8
1.1 Definitions 8
1.2 Examples 18
1.3 Variations on a theme 22
1.4 Three puzzles 26
2 Paths and cycles 32
2.1 Connectivity 32
2.2 Eulerian graphs and digraphs 40
2.3 Hamiltonian graphs and digraphs 47
2.4 Applications 52
3 Trees 61
3.1 Properties of trees 61
3.2 Counting trees 65
3.3 More applications 70
4 Planarity 80
4.1 Planar graphs 80
4.2 Euler's formula 86
4.3 Dual graphs 91
4.4 Graphs on other surfaces 96
5 Colouring graphs 101
5.1 Colouring vertices 101
5.2 Chromatic polynomials 107
5.3 Colouring maps 111
5.4 The four-colour theorem 117
5.5 Colouring edges 122
6 Matching,marriage and Menger's theorem 128
6.1 Hall'smarriage theorem 128
6.2 Menger's theorem 134
6.3 Network flows 138
7 Matroids 145
7.1 Introduction to matroids 145
7 2 Examples of matroids 149
7 3 Matroids and graphs 152
Appendix 1：Algorithms 158
Appendix 2：Table of numbers 161
List of symbols 162
Bibliography 163
Solutions to selected exercises 166
Index 181