You are here

A Beginner's Guide to Graph Theory

W. D. Wallis
Publication Date: 
Number of Pages: 
[Reviewed by
Fabio Mainardi
, on

The official birth date of graph theory is the publication by Euler in 1736 of the solution to the famous old problem of the seven bridges in Königsberg. (The original article in Latin is freely available on line.) Since then, the theory has grown hugely and has found applications to computer science (especially networks), management science (where graph theory often meets optimization theory) and even chemistry, condensed matter physics and social science.

As its title claims, this book is a gentle introduction to graph theory, presenting the main ideas and topics — Euler walks, Hamilton cycles, the salesman problem, trees, graph colouring, Ramsey theory. It is accessible to everyone, the only prerequisite being some acquaintance with elementary algebra.

This introductory book is addressed to a mixed audience — undergraduate mathematics majors, computer scientists, engineers — accordingly, the last three chapters are devoted to the algorithmic aspects and the applications to the study of flows in networks.

The profusion of examples, illustrations and exercises (with solutions) contribute to the great clearness of the exposition, so that this book is ideal as well for self-reading. The style is always concise and the essential techniques are well highlighted, clearly a result of many years of teaching on those topics. It is highly recommended to any student, or working scientist, wishing to explore for the fist time this fascinating area of mathematics.

Fabio Mainardi earned a PhD in Mathematics at the University of Paris 13. His research interests are mainly Iwasawa theory, p-adic L-functions and the arithmetic of automorphic forms. At present, he works in a "classe préparatoire" in Geneva. He may be reached at [email protected].


Preface.- Preface to the First Edition.- List of Figures.- Graphs.- Walks, Paths, and Cycles.- Connectivity.- Trees.- Linear Spaces Associated with Graphs.- Factorizations.- Graph Colorings.- Planarity.- Labeling.- Ramsey Theory.- Digraphs.- Critical Paths.- Flows in Networks.- Computational Considerations.- Communication Networks and Small Worlds.- References.- Hints.- Answers and Solutions.