图论（英文版） (2010 年度畅销榜NO.15462 )

　　本书并不是一本论文集，而是一系列讲稿的有机组合。本书涉及了Menger定理、重构、矩阵—树定理、Brooks定理、Grinberg定理、平面图等核心论题。在讲述时不仅关注原理本身，而且关注其推导过程。如果想对图论有个基本的了解，本书是最佳选择。另外，书中每一章都附有习题、注记和详尽的参考文献。
“相信本书会对在坚实的理论与技术基础上搭建起图论的大厦起到十分重要的作用。”
　　　　　　　　　　　　　　——Crispin St.J.A. Nash-Williams教授，里丁大学

Editor's Statement
Foreword
Introduction
Chapter I Graphs and Subgraphs
I.1 Definitions
1.2 Isomorphism
1.3 Subgraphs
1.4 Vertices of attachment
1.5 Components and connection
1.6 Deletion of an edge
1.7 Lists of nonisomorphic connected graphs
1.8 Bridges
1.9 Notes
Exercises
References
Chapter II Contractions and the Theorem of Menger
II.1 Contractions
II.2 Contraction of an edge
II.3 Vertices of attachment
II.4 Separation numbers
II.5 Menger's Theorem
II.6 Hall's Theorem
II.7 Notes
Exercises
References
Chapter III 2-Connection
III.1 Separable and 2-connected graphs
III.2 Constructions for 2-connected graphs
III.3 Blocks
III.4 Arms
III.5 Deletion and contraction of an edge
II1.6 Notes
Exercises
References
Chapter IV 3-Connection
IV.1 Multiple connection
IV.2 Some constructions for 3-connected graphs
IV.3 3-blocks
IV.4 Cleavages
IV.5 Deletions and contractions of edges
IV.6 The Wheel Theorem
IV.7 Notes
Exercises
References
Chapter V Reconstruction
V.I The Reconstruction Problem
V.2 Theory and practice
V.3 Kelly's Lemma
V.4 Edge-reconstruction
V.5 Notes
Exercises
References
Chapter VI Digraphs and Paths
VI.1 Digraphs
VI.2 Paths
VI.3 The BEST Theorem
VI.4 The Matrix-Tree Theorem
VI.5 The Laws of Kirchhoff
VI.6 Identification of vertices
VI.7 Transportation Theory
VI.8 Notes
Exercises
References
Chapter VII Alternating Paths
VII.1 Cursality
VII.2 The bicursal subgraph
VII.3 Bicursal units
VII.4 Alternating barriers
VII.5 f-factors and f-barriers
VII.6 The f-factor theorem
VII.7 Subgraphs of minimum deficiency
VII.8 The bipartite case
VII.9 A theorem of Erdos and Gallai
VII.10 Notes
Exercises
References
Chapter VIII Algebraic Duality
VIII.I Chain-groups
VIII.2 Primitive chains
VIII.3 Regular chain-groups
VIII.4 Cycles
VIII.5 Coboundaries
VIII.6 Reductions and contractions
VIII.7 Algebraic duality
VIII.8 Connectivity
VIII.9 On transportation theory
VIII.10 Incidence matrices
VIII.11 Matroids
VIII.12 Notes
Exercises
References
Chapter IX Polynomials Associated with Graphs
IX.1 V-functions
IX.2 The chromatic polynomial
IX.3 Colorings of graphs
IX.4 The flow polynomial
IX.5 Tait colorings
IX.6 The dichromate of a graph
IX.7 Some remarks on reconstruction
IX.8 Notes
Exercises
References
Chapter X Combinatorial Maps
X.1 Definitions and preliminary theorems
X.2 Orientability
X.3 Duality
X.4 Isomorphism
X.5 Drawings of maps
X.6 Angles
X.7 Operations on maps
X.8 Combinatorial surfaces
X.9 Cycles and coboundaries
X. 10 Notes
Exercises
References
Chapter XI Planarity
XI.1 Planar graphs
XI.2 Spanning subgraphs
XI.3 Jordan's Theorem
XI.4 Connectivity in planar maps
XI.5 The cross-cut Theorem
XI.6 Bridges
XI.7 An algorithm for planarity
XI.8 Peripheral circuits in 3-connected graphs
XI.9 Kuratowski's Theorem
XI.10 Notes
Exercises
References
Index

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.

W. T. Tutte已故著名数学家, 现代图论奠基人之一. 他于1948年获得剑桥大学博士学位, 1942年至1949年担任三一学院评论员, 1948年至1962年执教于多伦多大学. 他是加拿大皇家科学院院士, 曾被授予HenryMarshallTory奖. 1982年, 加拿大议会授予他IzaakWaltonKillam纪念奖. 除本书外, 他还著有拟阵论方面的书籍. 他生前还多年担任《Journal of Combinatorial Theory》杂志主编.