Introduction to graph theory

✍ Scribed by Robin J. Wilson

• Publisher: Addison Wesley
• Year: 1996
• Tongue: English
• Leaves: 177
• Edition: 4
• Category: Library

✦ Synopsis

Provides a basic foundation on trees, algorithms, Eulerian and Hamilton graphs, planar graphs and coloring, with special reference to four color theorem. Discusses directed graphs and transversal theory and related these areas to Markov chains and network flows. Paper.

✦ Table of Contents

Title page......Page 1
Copyright page......Page 2
Contents......Page 3
Preface to the fourth edition......Page 5
1 What is a graph?......Page 7
2 Definition......Page 14
3 Examples......Page 23
4 Three puzzles......Page 27
5 Connectivity......Page 32
6 Eulerian graphs......Page 37
7 Hamiltonian graphs......Page 41
8 Some algorithms......Page 44
9 Properties of trees......Page 49
10 Counting trees......Page 53
11 More applications......Page 57
12 Planar graphs......Page 66
13 Euler's formula......Page 71
14 Graphs on other surfaces......Page 76
15 Dual graphs......Page 79
16 Infinite graphs......Page 83
17 Colouring vertices......Page 87
18 Brooks' theorem......Page 92
19 Colouring maps......Page 94
20 Colouring edges......Page 98
21 Chromatic polynomials......Page 102
22 Definitions......Page 106
23 Eulerian digraphs and tournaments......Page 111
24 Markov chains......Page 115
25 Hall's 'marriage' theorem......Page 118
26 Transversal theory......Page 121
27 Applications of Hall's theorem......Page 124
28 Menger's theorem......Page 128
29 Network flows......Page 132
30 Introduction to matroids......Page 138
31 Examples of matroids......Page 141
32 Matroids and graphs......Page 145
33 Matroids and transversals......Page 149
Appendix......Page 153
Bibliography......Page 154
Solutions to selected exercises......Page 156
Index of symbols......Page 173
Index of definitions......Page 174