图论（英文版）

　　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. It 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 SainteLague's 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 K6nig, 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 undergraduates. 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-Lague's 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 vertexcolorings.
　　 So far there is one important omission, that of a theory of planarity. The graphs of interest in connection with squared rectangles and triangulated 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.