The present book has grown out of courses on graph theory given from time to time at Yale University. A first set of lectures on binary relations and graphs was presented before the American Mathematical Society at its summer meeting in Chicago, 1942. Since the manuscript to these lectures was not completed for publication at that time due to more urgent tasks it seems appropriate that this book should appear in the Colloquium Lecture Series of the society.
Graph theory as a mathematical discipline was created by Euler in his now famous discussion of the Königsberg Bridge Problem. However, Euler's article of 1736 remained an isolated contribution for nearly a hundred years. About the middle of the last century a resurgence of interest in the problems of graph theory took place, centered mainly in England. There were many causes for this revival of graph studies: The natural sciences had their influence through investigations of electrical networks and models for crystal and molecular structure; the development of formal logic led to the study of binary relations in the form of graphs. A number of popular puzzle problems could be formulated directly in terms of graphs and thus came the realization that many such questions include a mathematical nucleus of general importance. Most celebrated among them is the Four Color Map Conjecture which was first laid before the mathematicians by De Morgan around 1850. No other problem has occasioned as numerous and ingenious contributions to graph theory. Due to its simple formulation and exasperating evasiveness it still remains a powerful incitement to the examination of graph properties.
The present century has witnessed a steady development of graph theory which in the last ten to twenty years has blossomed out into a new period of intense activity. Clearly discernible in this process are the effects of the demands from new fields of applications: game theory and programming, communications theory, electrical networks and switching circuits as well as problems from biology and psychology.
As a consequence of these recent developments the subject of graphs is already so extended that it did not seem feasible to cover all its main ramifications within the framework of a single volume. In the present first volume of an intended two volume work the emphasis has been placed upon basic concepts and the results of particular systematic interest.
There exist very few books on graph theory; the mainstay has been the book by D. König (1936), which for its time gave a most excellent introduction to the subject. Strangely enough, until now there has been no book in English, in spite of the fact that many of the most important contributions to the subject . . .