The author encountered graph theory in high school, in the early thirties,
while reading Rouse Bali's book Mathematical Essays and Recreations. He
then learned of Euler paths (Sec. VI.3), map-colorings (dualized in Sec.
IX.3), factors of graphs (Sec. VII.6), and Tait colorings (Sec. IX.5) [5].
As an undergraduate at Cambridge he joined with R. L. Brooks,
C. A. B. Smith, and A. H. Stone in the study of their hobby-problem of
dissecting a square into unequal squares [3]. This soon called for much
graph theory. Ic was linked, through a "Smith diagram," with the study of
3-connected planar graphs (Sec. XI.7), and with Kirchhoff's Laws for
electrical circuits (Sec. VI.5). It was linked through rotor theory (Sec. VI,
Notes) with graph symmetry (Sec. 1.2). It was linked through the tree-number
(Sec. II.2) with the theory of graph functions satisfying simple recursion
formulae (Sec. IX. 1).
All this is explained in the Commentaries of [4]. That is one reason
why I do not discuss squared rectangles and the analogous triangulated
triangles in the present work. Another is that I visualize the book as a work
on pure graph theory, making no appeal either to point-set topology or to
elementary geometry.
I became acquainted with some graph-theoretical literature at Cam-
bridge. I read Sainte-Lagues description of the proof of Petersen's Theorem
(Sec. VII.6). I found the classical papers of Hassler Whitney, published in
1931-3, and the famous book of Denes Krnig, the first textbook devoted
entirely to graph theory. I was there at Cambridge at the time of the births
of Smith's Theorem (Sec. IX.5) [7] and Brooks' Theorem (Sec. IX.3) [2].
Stone's discovery of flexagons came a little later.
Having meditated upon these things for 45 years I now present some
of them in the present work. It is an attempt at the reference book I would
have liked to have in 1936-40. In electrical theory it is important to know
whether you have a connection between the two terminals, and what
happens when you remove a wire. Chapter I deals graph-theoretically with
these matters. Chapter II deals with the effect of contracting an edge, or
shall we say making a short circuit. The theory of 3-connection is discussed
in Chapter IV, and the halfway stage of 2-connection in Chapter III.
Chapter V, on reconstruction, is less directly related to squared squares and
rectangles. I came to it by way of reconstruction formulae for some of the
above-mentioned recursive graph functions [11].
Chapter VI concerns digraphs and a generalized theory of Kirchhoff's
Laws. It arose out of a study of triangulated triangles by the four under-
graduates. We were sometimes reproached for basing our mathematical
theory on physical laws. We protested, of course, that for us Kirchhoff's
Laws were axioms of a purely mathematical system, but we were glad to be
able to emphasize this by introducing generalized Laws, describing a kind of
electricity that never was on land or sea.
Chapter VII derives from Sainte-Lagues paper, with some gaps filled
and some extensions made. Chapter VIII is about cycles and coboundaries,
generalizations of Kirchhoff flows. It attempts to describe some parts of
graph theory algebraically, and most of it derives from my doctoral thesis of
1948 [9].
Chapter VIII is about the recursive graph functions. It derives from a
paper of 1947 [8]. It discusses the dichromatic polynomial, the dichromate,
the chromatic polynomial, and the flow-polynomial, all of which can be
referred to the theory of map-colorings and to the dual theory of vertex-
colorings.
So far there is one important omission, that of a theory of planarity.
The graphs of interest in connection with squared rectangles and triangu-
lated triangles are all planar, so Chapter X prepares for the introduction of
planarity by giving a general theory of maps on surfaces. But this is to be a
purely graph-theoretical work, and so the maps of Chapter X are structures
defined by purely combinatorial axioms. Surfaces are defined as classes
of maps. The discussion is an adaptation of the classical theory of
H. R. Brahana [1]. Planar maps can now be defined as maps of Euler
characteristic 2.
Chapter XI gives a theory of planarity. It gives duality theorems for
the tree-number and the dichromate, and it gives a combinatorial version of
Jordan's Theorem. It goes on to some tests for the planarity or nonplanarity
of a given graph, MacLane's and Kuratowski's among them. This part
derives from my paper "How to draw a graph," of 1964, but it skips the
actual drawing, that being a matter of elementary geometry rather than
graph theory.
I take this opportunity to express my indebtedness to Brooks, Smith,
and Stone, without whose missionary zeal I might now be writing on some
other subject.
|
