The flavor of this texbook is perhaps best conveyed by listing the chapters and their sections. 0. Fundamentals: Graphs. The degree of a vertex. Paths and cycles. Connectivity. Trees and forests. Bipartite graphs. Contraction and minors. Eulerian graphs. Algebraic concepts. Related concepts. 1. Matchings: Matchings in bipartite graphs. Matchings in general graphs. Coverings by disjoint paths. 2. Connectivity: 2-connected graphs and subgraphs. The structure of 3-connected graphs. The theorem of Menger. The theorem of Mader. Edge-disjoint spanning trees. Linking paths with given end vertices. 3. Graphs in the Plane: Topological prerequisites. Plane graphs. Drawings. Planarity: Kuratowski's theorem. Algebraic planarity criteria. Planarity and duality. 4. Colorings: Maps and colors of plane graphs. Vertex colorings. Edge colorings. List colorings. Perfect graphs. 5. Flows: Flows. Flows and circulations. Networks. k-flows for small k. Flows and colorings. Tutte's flow conjectures. 6. Substructures: Subgraphs. Topological minors. Minors. The Hadwiger conjecture. The regularity lemma. 7. Ramsey Theory for Graphs: Ramsey's theorem. Ramsey numbers of graphs. Ramsey induced. Ramsey theorems and connectivity. 8. Hamiltonian Cycles: Simple sufficient conditions. Hamiltonian cycles and degree sequence. Hamiltonian cycles in the square of a graph. 9. Random Graphs: The concept of random graphs. The probabilistic method. Properties of almost all graphs. Threshold functions and second moments. 10. Minors. Trees, and the WQO: Well-quasi-ordering. Trees: Kruskal's theorem. Tree decompositions. The theorem on minors.
A few results are included without proofs but, for the most
part, clean, concise arguments are provided. The exercises, 250
in all, are collected at the end of each chapter. These are followed
by notes concomitant with the text, e.g., they include sources
for many of the proofs, further references, and historical remarks.
Problems are an essential part of any textbook and the selection
here is appropriate. Some exercises are graded for difficulty.
Some state results that follow directly from theorems but are
required to be proved ab initio.
Several distinguishing features contribute to the comfortable
`feel' of this book. For example, symbols and terms being defined
are listed in the margin: these margins also contain extensive
cross referencing. The index contains the English equivalents
for technical terms. In addition, the author includes a brief
English to German dictionary of technical terminology. In the
Foreword he gives a web site address to which readers may send
errors or misprints: it contained no entries at the time of this
writing.
R.C. Entringer
Zentralblatt für Mathematik und ihre Grenzgebiete