Graph theory

Title page......Page 1
Preface......Page 5
The Konigsberg bridge problem......Page 11
Electric networks......Page 12
Chemical isomers......Page 13
Around the world......Page 14
Graph theory in the 20th century......Page 15
Varieties of graphs......Page 18
Walks and connectedness......Page 23
Degrees......Page 24
The problem of Ramsey......Page 25
Extremal graphs......Page 27
Intersection graphs......Page 29
Operations on graphs......Page 31
Cutpoints, bridges, and blocks......Page 36
Block graphs and cutpoint graphs......Page 39
Characterization of trees......Page 42
Centers and centroids......Page 45
Block-cutpoint trees......Page 46
Independent cycles and cocycles......Page 47
Matroids......Page 50
Connectivity and line-connectivity......Page 53
Graphical variations of Menger's theorem......Page 57
Further variations of Menger's theorem......Page 62
6 Partitions......Page 67
Eulerian graphs......Page 74
Hamiltonian graphs......Page 75
Some properties of line graphs......Page 81
Characterizations of line graphs......Page 83
Special line graphs......Page 87
Line graphs and traversability......Page 89
Total graphs......Page 92
1- factorization......Page 94
2-factorization......Page 98
Arboricity......Page 100
Coverings and independence......Page 104
Critical points and lines......Page 107
Line-core and point-core......Page 108
Plane and planar graphs......Page 112
Outerplanar graphs......Page 116
Kuratowski's theorem......Page 118
Other characterizations of planar graphs......Page 123
Genus, thickness, coarseness, crossing number......Page 126
The chromatic number......Page 136
The Five Color Theorem......Page 140
The Four Color Conjecture......Page 141
The Heawood map-coloring theorem......Page 145
Uniquely colorable graphs......Page 147
Critical graphs......Page 151
Homomorphisms......Page 153
The chromatic polynomial......Page 155
The adjacency matrix......Page 160
The incidence matrix......Page 162
The cycle matrix......Page 164
The automorphism group of a graph......Page 170
Operations on permutation groups......Page 173
The group of a composite graph......Page 175
Graphs with a given group......Page 178
Symmetric graphs......Page 181
Highly symmetric graphs......Page 183
Labeled graphs......Page 188
Polya's enumeration theorem......Page 190
Enumeration of graphs......Page 195
Enumeration of trees......Page 197
Power group enumeration theorem......Page 201
Solved and unsolved graphical enumeration problems......Page 202
Digraphs and connectedness......Page 208
Directional duality and acyclic digraphs......Page 210
Digraphs and matrices......Page 212
Tournaments......Page 215
Appendix I Graph Diagrams......Page 223
Appendix II Digraph Diagrams......Page 235
Appendix III Tree Diagrams......Page 241
Bibliography......Page 247
Index of Symbols......Page 279
Index of Definitions......Page 283