Introduction to Graph Theory

In recent years, graph theory, being an important mathematical tool in such diverse fields of knowledge as operations research, chemistry, sociology, or genetics, has become an independent subject. Robin Wilson's book is widely used as a textbook for undergraduate courses in mathematics, computer science, and economics, as well as an introduction to the subject for students in non-mathematical specialties. The introductory chapters provide a basic course containing definitions and examples. They cover connectivity, Eulerian and Hamiltonian paths and cycles, as well as trees. This is followed by two chapters on planar graphs and graph coloring, with a separate discussion of the four color problem. The next chapter is dedicated to the theory of transversals and connectivity with applications to network flows. The final chapter on matroid theory ties together the material from the previous chapters. The appendix discusses algorithms and their efficiency. The text of this new edition has been thoroughly revised, and some sections have been reorganized and renumbered. New material has been added, particularly related to the proof of the four color theorem, the strengthening of rectangular frameworks, and algorithms. The number of exercises has increased, and more solutions are presented than before.