text:
Principal Handbook of combinatorics
Handbook of combinatoricsRonald L Graham, Martin Grötschel, László Lovász
You may be interested in
Most frequently terms
graph theory273
You can write a book review and share your experiences. Other readers will always be interested in your opinion of the books you've read. Whether you've loved the book or not, if you give your honest and detailed thoughts then people will find new books that are right for them.
HANDBOOK OF COMBINATORICS Volume 1 edited by R.L. GRAHAM AT&T Bell Laboratories, Murray Hill, NJ, USA M.GRUTSCHEL Konrad-Zuse-Zentrumjurlnformationstechnik, Berlin-Wilmersdorf, Germany L.LOVASZ Yale University, New Haven, CT, USA 1995 1995 ELSEVIER AMSTERDAM-LAUSANNE-NEW YORK ¦ THEMITPRESS OXFORD - SHANNON TOKYO CAMBRIDGE, MASSACHUSETTS ELSEVIER SCIENCE B.V. Sara Burgerhartstraat 25 P.O. Box 211,1000 AE Amsterdam, The Netherlands Co-publishers for the United States and Canada: The MIT Press 55 Hayward Street Cambridge, MA 02142, U.S.A. Elsevier Science B.V. ISBN: 0-444-82346-8 (Volume 1) ISBN:0-444-88002-X(Sctofvols 1 and2) The MIT Press ISBN: 0-262-07170-3 (Volume 1) ISBN:0-262-07169-X(Setofvolsland2) © 1995 Elsevicr Science B.V. All rights reserved. No pan of this publication may be reproduced, stored in a retrieval system or transmitted in any form or by any means, electronic, mechanical, photocopying, recording or otherwise, without the prior written permission of the publisher, Elsevier Science B. V., Copyright & Permissions Department, P.O. Box 521, 1000 AM Amsterdam, The Netherlands. Special regulations for readers in the U.S.A.: This publication has been registered with the Copyright Clearance Center Inc. (CCC), 222 Rosewood Drive, Danvers, MA 01923. Information can be obtained from the CCC about conditions under which photocopies of pans of this publication may be made in the U.S. A. All other copyright questions, including photocopying outside of the U.S.A., should be referred to the publisher, unless otherwise specified. No responsibility is assumed by the publisher for any injury and/or damage to persons or property as a matter of products liability, negligence or otherwise, or from any use or operation of any methods, products, instructions or ideas contained fii the material herein. This book is printed on acid-free paper. Printed inThe Netherlands Preface Combinatorics belongs to those areas of mathematics having experienced a most impressive growth in recent years. This growth has been fuelled in large part by the increasing importance of computers, the needs of computer science and demands from applications where discrete models play more and more important roles. But also more classical branches of mathematics have come to recognize that combi- combinatorial structures are essential components of many mathematical theories. Despite the dynamic state of this development, we feel that the time is ripe for summarizing the current status of the field and for surveying those major re- results that in our opinion will be of long-term importance. We approached leading experts in all areas of combinatorics to write chapters for this Handbook. The response was overwhelmingly enthusiastic and the result is what you see here. The intention of the Handbook is to provide the working mathematician or com- computer scientist with a good overview of basic methods and paradigms, as well as important results and current issues and trends across the broad spectrum of com- combinatorics. However, our hope is that even specialists can benefit from reading this Handbook, by learning a leading expert's coherent and individual view of the topic. As the reader will notice by looking at the table of contents, we have structured the Handbook into five sections: Structures, Aspects, Methods, Applications, and Horizons. We feel that viewing the whole field from different perspectives and taking different cross-sections will help to understand the underlying framework of the subject and to see the interrelationships more clearly. As a consequence of this approach, a number of the fundamental results occur in more than one chap- chapter. We believe that this is an asset rather than a shortcoming, since it illustrates different viewpoints and interpretations of the" results. We thank the authors not only for writing the chapters but also for many helpful suggestions on the organization of the book and the presentation of the material. Many colleagues have contributed to the Handbook by reading the initial versions of the chapters and by making proposals with respect to the inclusion of topics and results as well as the structuring of the chapters. We are grateful for the significant help we received. Even though this Handbook is quite voluminous, it was inevitable that some areas of combinatorics had to be left out or were not covered in the depth they deserved. Nevertheless, we believe that the Handbook of Combinatorics presents a comprehensive and accessible view of the present state of the field and that it will prove to be of lasting value. Ronald Graham Martin Grutschel L?szl6 Lovasz Contents Volume I Preface v List of Contributors xi Part I: Structures 1 Graphs 1. Basic Graph Theory: Paths and Circuits 3 J.A. Bondy 2. Connectivity and Network Flows 111 A. Frank 3. Matchings and Extensions 179 W.R. Pulleyblank 4. Colouring, Stable Sets and Perfect Graphs 233 B. Toft Appendix to Chapter 4: Nowhere-Zero Flows 289 P.D. Seymour 5. Embeddings and Minors 301 C. Thomassen 6. Random Graphs 351 M. Karonski Finite Sets and Relations 7. Hypergraphs 381 P. Duchet 8. Partially Ordered Sets 433 W.T. Trotter Matroids 9. Matroids: Fundamental Concepts 481 D.J.A. Welsh 10. Matroid Minors 527 P.D. Seymour 11. Matroid Optimization and Algorithms 551 R.E. Bixby and W.H. Cunningham viii Contents Symmetric Structures 12. Permutation Groups P.]. Cameron 13. Finite Geometries P.J. Cameron 14. Block Designs A.E. Brouwer 15. Association Schemes A .E. Brouwer and W.H. Haemers 16. Codes J.H. van Lint Combinatorial Structures in Geometry and Number Theory 17. Extremal Problems in Combinatorial Geometry P. Erdos and G. Purdy 18. Convex Polytopes and Related Complexes V. Klee and P. Kleinschmidt 19. Point Lattices J.C Lagarias 20. Combinatorial Number Theory C. Pomerance and A. Sdrkozy Author Index Subject Index Volume II 611 647 693 747 773 809 875 919 967 XIII LIX Preface List of Contributors Part II: Aspects 21. Algebraic Enumeration I.M. Gessel and R.P. Stanley 22. Asymptotic Enumeration Methods A.M. Odlyzko 23. Extremal Graph Theory B. Bollobds J 24. Extremal Set Systems P. Frank! 25. Ramsey Theory /. Nesetril 1019 1021 1063 1231 1293 1331 Contents 26. Discrepancy Theory J. Beck and V.T. Sos 27. Automorphism Groups, Isomorphism, Reconstruction L. Babai 28. Combinatorial Optimization M. Grotschel and L. Lovasz 29. Computational Complexity D.B. Shmoys and Ё. Tardos Part III: Methods 30. Polyhedral Combinatorics A. Schrijver 31. Tools from Linear Algebra CD. Godsil Appendix L. Lovasz 32. Tools from Higher Algebra N. Alon 33. Probabilistic Methods J. Spencer 34. Topological Methods A. Bjorner Part IV: Applications 35. Combinatorics in Operations Research A.WJ. Kolen and J.K. Lenstra 36. Combinatorics in Electrical Engineering and Statics A. Recski 37. Combinatorics in Statistical Physics CD. Godsil, M. Grotschel and D.J.A. Welsh 38. Combinatorics in Chemistry D.H. Rouvray 39. Applications of Combinatorics to Molecular Biology M.S. Waterman 40. Combinatorics in Computer Science L. Lovasz, D.B. Shmoys and E. Tardos 41. Combinatorics in Pure Mathematics L. Lovasz, L. Pyber, D.J.A. Welsh and G.M. Ziegler Part V: Horizons 42. Infinite Combinatorics A. Hajnal 1405 1447 1541 1599 1647 1649 1705 1740 1749 1785 1819 1873 1875 1911 1925 1955 1983 2003 2039 2083 2085 Contents 43. Combinatorial Games R.K. Guy 44. The History of Combinatorics N.L. Biggs, E.K. Lloyd and RJ. Wilson Author Index Subject Index 2117 2163 XIII LIX List of Contributors Alon, N., Tel Aviv University, Tel Aviv (Ch. 32). Babai, L., Eotvos University, Budapest and University of Chicago, Chicago, IL (Ch. 27). Beck, J., Rutgers University, New Brunswick, NJ (Ch. 26). Biggs, N.L., University of London, London (Ch. 44). Bixby, R.E., Rice University, Houston, TX (Ch. 11). Bjorner, A., Royal Institute of Technology, Stockholm (Ch. 34). Bollobas, В., University of Cambridge, Cambridge and Louisiana State Universi- University, Baton Rouge, LA (Ch. 23). Bondy, J.A., Universite Claude Bernard Lyon 1, Villeurbanne and University of Waterloo, Waterloo, Ont. (Ch. 1). Brouwer, A.E., Eindhoven University of Technology, Eindhoven (Chs. 14, 15). Cameron, P.J., Queen Mary and Westfteld College, London (Chs. 12, 13). Cunningham, W.H., University of Waterloo, Waterloo, Ont. (Ch. 11). Duchet, P., IMAG, Laboratoire de Structures Discretes et de Didactique, Grenoble Cedex (Ch. 7). Erdos, P., Hungarian Academy of Sciences, Budapest (Ch. 17). Frank, A., Eotvos University, Budapest (Ch. 2). Frankl, P., CNRS, Paris (Ch. 24). Gessel, I.M., Brandeis University, Waltham, MA (Ch. 21). Godsil, CD., University of Waterloo, Waterloo, Ont. (Chs. 31, 37). Grdtschel, M,, Konrad-Zuse-Zentrum fur Informationstechnik, Berlin-Wilmers- dorf (Chs. 28, 37). Guy, R.K., University of Calgary, Calgary, Alta. (Ch. 43). Haemers, W.H., Tilburg University, Tilburg (Ch. 15). , Hajnal, A., Hungarian Academy of Sciences, Budapest (Ch. 42). Karoriski, M., Adam Mickiewicz University, Poznan and Emory University, Atlanta, GA (Ch. 6). Klee.V., University of Washington, Seattle, WA (Ch. 18). Kleinschmidt, P., Universitat Passau, Passau (Ch. 18). Kolen, A.W.J., University of Limburg, Maastricht (Ch. 35). Lagarias, J.C., AT&T Bell Laboratories, Murray Hill, NJ (Ch. 19). Lenstra, J.K., Eindhoven University of Technology, Eindhoven and Centre for Mathematics and Computer Science, Amsterdam (Ch. 35). Lloyd, E.K., University of Southampton, Southampton (Ch. 44). Lovasz, L., Yale University, New Haven, CT (Chs. 28, 31, 40, 41). Nesetfil, J., Charles University, Prague (Ch. 25). Odlyzko, A.M., AT&T Bell Laboratories, Murray Hill, NJ (Ch. 22). Pomerance, C, University of Georgia, Athens, GA (Ch. 20). xii List of Contributors Pulleyblank, W.R., IBM, Thomas J. Watson Research Center, Yorktown Heights, NY (Ch. 3). Purdy, G., University of Cincinnati, Cincinnati, OH (Ch. 17), Pyber, L., Hungarian Academy of Sciences, Budapest (Ch. 41). Recski, A., Technical University of Budapest, Budapest (Ch. 36). Rouvray, D.H., The University of Georgia, Athens, GA (Ch. 38). Sarkozy, A., Hungarian Academy of Sciences, Budapest (Ch. 20). РяТ*1" Т Schrijver, A., Centrum voor Wiskunde en Informatica, Amsterdam (Ch. 30). ¦*- **-* ^ -*- Seymour, P.D., Bell Communications Research, Morristown, NJ (Appendix to ел л л ch. 4, сь. io) Structures Shmoys, D.B., Cornell University, Ithaca, NY (Chs. 29, 40). Sos, V.T., Hungarian Academy of Sciences, Budapest (Ch. 26). Spencer, J., New York University, New York, NY (Ch. 33). Stanley, R.P., Massachusetts Institute of Technology, Cambridge, MA (Ch. 21). Tardos, Ё., Cornell University, Ithaca, NY (Chs, 29, 40). Thomassen, C, The Technical University of Denmark, Lyngby (Ch. 5). Toft, В., Odense University, Odense (Ch. 4). Trotter, W.T., Arizona State University, Tempe, AZ (Ch. 8). Van Lint, J.H., Eindhoven University of Technology, Eindhoven (Ch. 16). Waterman, M.S., University of Southern California, Los Angeles, С A (Ch. 39). Welsh, D.J.A., University of Oxford, Oxford (Chs. 9, 37, 41). Wilson, R.J., The Open University, Milton Keynes (Ch. 44). Ziegler, G.M., Konrad-Zuse-Zentrum fiir Informationstechmk, Beriin-Wilmers- dorf {C\i. 41). CHAPTER 1 Basic Graph Theory: Paths and Circuits J.A. BONDY Institut de Mathematiques et Informatique, Universite Claude Bernard Lyon I, 69622 VILLEURBANNE Cedex, France and Faculty of Mathematics, University of Waterloo, Waterloo, Om. N2L 3G1, Canada Contents 1. Basic concepts 5 1.1. Graphs 5 1.2. Subgraphs and minors 7 1.3. Walks 9 1.4. Connection 9 1.5. Extremal graphs 11 1.6. Search trees 12 1.7. Directed graphs ..,. 15 1.8. Hypergraphs 18 2. Hamilton paths and circuits in graphs 20 2.1. Dirac"s theorem 20 2.2. Generalizations of Dirac's theorem 23 3. Hamilton paths and circuits in digraphs 28 3.1. Redei's theorem 28 3.2. Generalizations of Redei's theorem 29 4. Fundamental parameters 33 4.1. Connectivity and edge connectivity , 34 4.2. Stability number 40 4.3. Matching number 46 4.4. Chromatic number and edge chromatic number 48 4.5. Toughness 51 5. Fundamental classes of graphs and digraphs 54 5.1. Bipartite graphs 54 5.2. Planar graphs 55 5.3. Regular graphs and vertex-transitive graphs 59 5.4. Line graphs and claw-free graphs , 65 5.5. Oriented graphs and tournaments 67 HANDBOOK OF COMBINATORICS Edited by R. Graham, M. Grotsche] and L. Lovasz © 1995 Elsevier Science B.V. All rights reserved 4 J.A. Bondy 6. Special proof techniques for paths and circuits 69 6.1. Thomason's lemma 69 6.2. Posa's lemma 70 6.3. Woodall"s hopping lemma 72 7. Lengths of circuits 74 7.1. Circuits of given length modulo к 75 7.2. Circuits of given length 76 7.3. Circuits of many lengths 77 7.4. Circuits of all lengths 77 7.5. The number of circuits 78 8. Packings and coverings by paths and circuits 80 8.1. Packings and coverings of hypergraphs 80 8.2. Packings by paths and circuits 81 8.3. Coverings by circuits 84 8.4. Partitions into paths and circuits 85 8.5. Decompositions into paths and circuits 86 8.6. Decompositions into Hamilton circuits 88 8.7. Compatible circuit decompositions 90 8.8. Double covers 91 References 94 Basic graph theory: Paths and circuits 5 Our purpose in this chapter is twofold: to introduce the basic concepts and tech- techniques of graph theory, and to develop that part of the theory concerned with paths and circuits. We have attempted to weave these two strands together, pro- proceeding from fundamental notions and elementary observations to more sophisti- sophisticated concepts and methods, much as one does when engaged in research. One of the attractive features of the subject is the wealth of simply stated but challenging open problems, and we have included a large number of these. It must be empha- emphasized that the literature on paths and circuits is extensive. Thus what is presented here is necessarily a selection. Nevertheless, our hope is that, after studying this chapter, the reader will be well equipped to embark on the chapters dealing with particular aspects of graph theory. Circuits in graphs are treated in depth in the books of Walther and Voss A974) and Voss A991). There are also many survey articles on particular aspects of the topic. We recommend, in particular, the arti- articles of Carsten Thomassen. Besides their substantial contributions to tjie theory of graphs, each includes an informed and stimulating discussion of the question under consideration and its links to related matters. 1. Basic concepts I.I. Graphs A graph G consists of a nonempty set V(G) of elements, called vertices or nodes, and a set E(G) of elements called edges, together with a relation of incidence that associates with each edge two vertices, called its ends. Two graphs G and H are isomorphic if there are bijections в : V(G) -» V(H) and ф :E(G) -> E(H) such that vertex v and edge e are incident in G if and only if vertex 9(v) and edge ф(е) are incident in H. The pair of mappings (в,ф) is an isomorphism from G to H. An edge with identical ends is a loop and one with distinct ends is a link. Two or more edges with the same pair of ends are multiple edges. The two ends of an edge are said to be joined by the edge and to be adjacent to one another; adjacent vertices are also referred to as neighbours. An edge with ends x and у is denoted by the unordered pair xy. The number of vertices of a graph G is called its order, the number of edges its size; these parameters are denoted by v(G) and e(G), respectively. A multigraph is one with no loops, a simple graph one with neither loops nor multiple edges. A graph it finite if both its vertex set and its edge set are finite, and infinite otherwise. This chapter is devoted entirely to finite graphs. Quite different techniques are needed for dealing with infinite graphs. These are discussed in the survey by Thomassen A983e) and also in chapter 42 by Hajnal. Graphs are so named because they can be represented pictorially, a vertex being indicated by a point and an edge by a line joining the points representing its ends; flg. 1 depicts the five Platonic graphs, the graphs of the Platonic solids. The graph of the tetrahedron in flg. 1 is an example of a complete graph: any two of its vertices J.A. Bondy Tetrahedron Octahedron Icosohedron Figure 1. The Platonic graphs. Dodecahedron are joined by an edge. An empty graph, by contrast, is one with no edges. The simple complete graph on n vertices is denoted by К". A graph is bipartite if its vertex set can be partitioned into subsets X and Y so that each edge has one end in X and one end in Y; such a partition (A", Y) is called a bipartition of the graph. A bipartite graph G with bipartition (A", Y) is denoted by G(X, Y). Such a graph is balanced if \X\ = \Y\ and complete if each vertex of X is joined to each vertex of Y; the graph of the cube in fig. 1 is a balanced bipartite graph. The simple complete bipartite graph G(X, Y) in which |A"| = m and |У| =я is denoted by KmJl; if m = 1, such a graph is called a star. The graphs K5 and Кз з are known as the Kuratowski graphs because they feature in a fundamental theorem of K. Kuratowski (Theorem 5.4); JC3 3 is also sometimes referred to as the Thomsen graph. It is sometimes convenient to represent the relations of adjacency and incidence in a graph by matrices. The adjacency matrix A(G) is the matrix (am) whose rows and columns are indexed by the vertices of G, а"" being the number of edges of G joining vertices и and v. The incidence matrix B(G) is the matrix (bvc) whose rows are indexed by the vertices of G and columns by the edges of G, bm being the number of times vertex v and edge e are incident; so bvt := 2 if e is a loop at v, bve := 1 if e is a link at v, and Ь" := О otherwise. As a general rale, the symbol specifying the graph (typically G) is dropped from notation if the context makes clear which graph is being discussed; vertex and edge sets are then denoted simply by V and E, and adjacency and incidence matrices by A and B. By the same tokfjn, the notation G(V,E) specifies a graph G with vertex set V and edge set E. An exception to this rule is the frequent use of n for the order, and occasionally m for the size, the letters v and e always denoting vertices and edges, respectively. The set of neighbours of a vertex и in a graph G is denoted by Nc{v). In a simple graph, the number of neighbours of a vertex is called its degree. More generally, Basic graph theory: Paths and circuits 7 the degree of a vertex v in a graph G is the number of edges of G incident with u, a loop counting as two edges. A graph is d-regular if each vertex has degree d, and regular if it is d-regular for some d. A graph is even if each vertex is of even degree. The degree of a vertex и in a graph G is denoted by dG(v), the minimum, maximum, and average degrees of the vertices of a graph G by S(G), A(G), and d(G), respectively. An isolated vertex is a vertex of degree zero, a leaf one of degree one. The number of edges in a graph and the degrees of its vertices are linked by a simple identity due to Euler A736). Proposition 1.1. For any graph G, Proof (by counting in two ways). We consider the incidence matrix В := (/>",.) of G and compute the sum of its entries in two ways: fc» = ?2=2,@. ? We have drawn attention to the proof technique used here, counting in two ways, because it is one that is frequently employed in combinatorial arguments. Further techniques will be highlighted as they are encountered; some of these are of general applicability, while others are designed specifically to study paths and circuits in graphs. Corollary 1.2. In any graph, the number of vertices of odd degree is even. 1.2. Subgraphs and minors Let G and H be graphs. If V(H) с V(G) and E(H) С E(G), and if every edge of H has the same pair of ends in Я as it has in G, the graph H is called a subgraph of G and the graph G a supergraph of H\ these relationships are denoted by Я С G and G^>H, respectively. We also say that H is contained in G and that G contains H. A subgraph or supergraph Я of G spans G if V(H) = V{G). The union of two subgraphs Gi and G2 of G is the subgraph Gi U Gj with vertex set V(Gi) UF(G2) and edge set E(G,) и?(G2). Likewise the intersection of G\ and G2 is the subgraph Gj nG2 with vertex set V{G\) n V(G2) and edge set ?(Gi)n?(G2). If 5 is a set of edges of a graph G(V,E), the graph whose vertex set is V and whose edge set is E \ S is a subgraph of G-. Likewise, if S is a set of vertices of G, the subgraph of G whose vertex set is V \ S and whose edge set consists of those edges of G with both ends in V \ S is a subgraph of G. In both instances, this subgraph is denoted by G \ S, and is said to be obtained by deleting S from G. If Я is a subgraph of G, we denote the subgraph G \ V(H) simply by G \ H. J.A. Bondy If 5 is a set of unordered pairs of vertices of G(V,E), the graph whose vertex set is V and whose edge set is ? и 5 is a spanning supergraph of G. This graph is denoted by G + S, and is said to be obtained by adding S to G; addition and deletion of edges are inverse operations. One may also add a set S of vertices to a graph. In this case, the resulting graph depends on which edges incident to the vertices of S are also added. If all pairs uv with и e S and v e V are added, and no others, the resulting graph is denoted by G + S. If S is a set of edges of G, the graph whose vertex set consists of all ends of edges in 5 and whose edge set is S is a subgraph of G. Likewise, if S is a set of vertices of G, the graph whose vertex set is 5 and whose edge set consists of those edges of G with both ends in S is a subgraph of G. In both instances, this subgraph is denoted by G[S] and is called the subgraph of G induced by S. Any subgraph of a graph may be obtained by deleting appropriate vertices and edges. Similarly, any spanning subgraph may be obtained by deleting edges, any vertex-induced subgraph by deleting vertices, and any edge-induced subgraph by deleting edges and isolated vertices. The subgraphs of a graph can be represented algebraically by their incidence matrices, but it turns out to be more fruitful to identify a subgraph with the char- characteristic function of its edge set. Let Я be a set. The characteristic function of a subset S of E is the function %s ¦ E —* GFB) defined by Xs(e) ~ ifeeS, 0 The functions xs form a vector space over GFB). When E is the edge set of a graph G, this vector space is called the edge space of G, and may be regarded as the set of edge-induced subgraphs of G, the sum of two such subgraphs G[S] and G[T] being G\SAT], where Л denotes symmetric difference. Families of subgraphs that are closed under this operation are thus of particular interest. The even subgraphs of G constitute such a family, and form a vector space %{G) over GFB) called the cycle space of G. (Originally, even graphs were called cycles. To avoid confusion, we have chosen not to adopt this name, because it is also commonly used for what we shall call a circuit.) As noted earlier, deletion and addition of edges are inverse operations. Another operation closely related to deletion, but in a more subtle way, is that of contrac- contraction. If 5 is a set of edges of a graph G, the graph derived from G by deleting 5 and identifying each pair of ends of the edges of 5 is said to be obtained by contracting S, and is denoted by G/S. If Я is a subgraph of G, we denote the contraction G/E(H) simply by G/H. A minor of a graph G is any graph obtain- obtainable from G by means of a seqi^nce of vertex deletions, edge deletions and edge contractions. Minors play a very important role in the structural theory of graphs. In particular, the absence of a particular graph as a minor has a profound effect on the properties of a graph. The survey by Robertson and Seymour A985) gives a good overview of this topic. Minors of graphs are discussed also in chapter 5 by Thomassen. Basic graph theory: Paths and circuits 9 1.3. Walks A walk in a graph G is a sequence W := Uoeiuie2 ¦¦¦eivi, where vo,t;i,...,v( are vertices of G, ei,e2,...,et are edges of G, and u,_i and v-, are the ends of e,-, 1 ^ i «: (.. In a simple graph, a walk is completely specified by its sequence of vertices, UqUi ¦¦¦vi. The vertex v0 is the tail of W, the vertices v i,..., vt-\ its internal vertices, and the vertex vt its head] the tail and head are often referred to as the ends of W. The walk W is described as a va-walk or a v<>v/-walk if, as is often the case, one wishes to specify explicitly one or both of its ends; one also says that W connects v0 and vt. The walk W is open if v0 ф vt and closed if vo = v,. The length of W is its number of edges, namely (; the parity of W is the parity of its length. We say that vertex v, precedes vertex v: on IV if i <;', and indicate this rela- relationship by the notation v, X Vj. If u, precedes vh the walk vteMVui ¦ • D^i^Uy is referred to as the ViVj-segment of W, and maybe denoted by W(u,,i>;], 1V(uj_i,Uj], lV[u,,Bj4i) or iy(uj_i,u;+i), as convenient; or by W[v,,v,], to indicate traversal of the segment in the opposite sense. The walk W is a trail if its edges е\,ег,..-,е/ are distinct, and a path if its vertices va,vi,...,vt are distinct. Note that a ugv(-walk of minimum length is necessarily a DoU(-path. A closed trail of positive length whose vertices (apart from its ends) are distinct is called a circuit. Dirac A952) found a link between the length of a longest path or circuit in a graph and the minimum degree. Theorem 13. Let G be a simple graph of minimum degree 8. Then (i) G contains a path P of length at least S; (ii) // S ^ 2, G contains a circuit С of length at least в +1. Proof (by choosing a maximal path). Let P := vc,vt ¦¦ ¦ vt be a maximal path of G (one that cannot be extended from either end). Then all the neighbours of i>o ue on P. Setting к := max {i: vov, 6 ?}, we have к > d(v0) > 5. Thus P is of length at least S and, if 5 > 2, С := uoui ¦ • ¦ vkva is a circuit of length at least 5 + 1. D A circuit decomposition of a graph is a partition of its edge set into circuits. For a graph to have a circuit decomposition, each vertex must clearly be of even degree. Veblen A912) proved the converse statement. Theorem 1.4. A graph is even if and only if it admits a circuit decomposition. Proof. A graph with a circuit decomposition is even because each vertex is inci- incident with either zero or two edges of any circuit. On the other hand, a nonempty even graph has at least one circuit, by Theorem 1.3(ii), and the subgraph obtained on deleting the edges of this circuit is even. Sufficiency now follows by induction on e(G). ? 1.4. Connection A graph is connected if any two of its vertices are connected by a path. A com- component of a graph G is a maximal connected subgraph of G (that is, a connected 10 J.A. Bandy subgraph contained in no other connected subgraph). The number of components of a graph G is denoted by c(G). The vertices and edges of an дгу-path form a connected subgraph in which the ends x and у have degree one and the internal vertices have degree two (unless the path is of length zero, in which case x — у has degree zero); similarly, the vertices and edges of a circuit form a connected 2-regular subgraph. The terms path and circuit will frequently be used to refer to such subgraphs. Circuits are very often called cycles, they are also sometimes re- referred to as polygons, short ones being given suggestive geometrical names: digon, triangle, quadrilateral, and so on. The distance d(x, y) between two vertices x and у in a graph is the length of a shortest xy-path in G, if there is one; otherwise their distance is denned to be infinite. The diameter of a graph is the maximum distance between its vertices. Thejirth of a graphjsjhejength °f a shortest circuit, jf there js one; otherwise thff_girlh is_tjgfingHjn_he /его. _ ~ A connected graph G is separable if it contains subgraphs Gi and Gi, and a vertex v, such that (a) G]UG2 = G, (b) G, nG2 = {v}, and (c) G; / {v}, i = 1,2. Otherwise, G is nonseparable. A block of a connected graph is a maximal nonseparable subgraph; the blocks of a disconnected graph are the blocks of its components. A cut vertex of a connected graph G is any vertex v satisfying conditions (b) and (c) above for some pair G\, Gi of subgraphs of G satisfying (a). The cut vertices of a disconnected graph are denned to be the cut vertices of its components. Thus и is a cut vertex of G if and only if G \ v has more components than G, unless v is incident to a loop and at least one other edge. Analogously, we define a cut edge oi a graph G to be an edge e such that G \ e has more components than G; equivalently, a cut edge is one that belongs to no circuit. The circuits of a graph lie entirely within its blocks. Thus, where circuits are con- concerned, nonseparability is a natural condition to impose. Hartman A983) strength- strengthened Theorem 1.3 (ii) for nonseparable graphs by showing that the circuits of length at least S +1 in a simple nonseparable graph G of minimum degree S gen- generate the cycle space of G, unless 5 is odd and G = KM. If such a graph has an odd circuit, it therefore has an odd circuit of length at least 5 + 1, unless 5 is odd and the graph is KM. A graph is acyclic, or a forest, if it contains no circuit or, equivalently, if each of its edges is a cut edge. The following basic property of forests was first noted by Listing A862). Proposition LS. Let G be a forest. Then Proof (by induction). The assertion holds if e(G) = 0, since in this case each com- component is a single vertex. Assume that e(G) > 0 and that the assertion holds for all forests on fewer than e(G) edges. Let G' be a subgraph of G obtained by deleting any one edge. Then G' is a forest with e(G) - 1 edges, v(G) vertices and c(G) + 1 Basic graph theory: Paths and circuits components. By the induction hypothesis, applied to G', e(G) - v(G) + cifi) = e(G) - 1 - v(G) + c(G) +1 Thus the assertion holds for all forests. ? A tree is a connected acyclic graph. It follows from Propositions 1.1 and 1.5 that every tree on two or more vertices has at least two vertices of degree one; such vertices are called leaves. Any connected graph, when viewed as an assemblage of its blocks, has the structure of a tree. More precisely, the block cut-vertex tree of a connected graph G is the tree H whose vertices are the blocks and the cut vertices of G, a block and cut vertex being adjacent in H if the block includes the cut vertex in G: H is connected because G is, and acyclic because a block is a maximal nonseparable subgraph. The blocks of G corresponding to the leaves of H are the endblocks of G. Every connected graph contains a spanning tree, a spanning subgraph which is a tree. In fact, the spanning trees are precisely the spanning subgraphs that are connected and are minimal with respect to the property. They are also the spanning subgraphs that are acyclic and are maximal with respect to the property, and thus can be "grown" by starting with one vertex and adding edges and vertices one by one. This latter viewpoint is of fundamental importance in both theoretical and applied contexts, as we shall see shortly in the section on search trees. Each spanning tree Г of a connected graph G determines a basis Чт of its cycle space $ in a natural way. For each edge e of G not in T, the subgraph T + e contains a unique circuit C,. The set 4T of all such circuits is a basis for 4: it is independent because Ce is the only circuit in %T that includes e, and it generates 4 because any even subgraph H of G can be expressed in the form «= ? ct. eHEI,H)\E{T) To see this, it suffices to observe that H + Y.eeE(m\Em C« 's an even subgraph contained in T, and hence is empty by Theorem 1.4. Because the cycle space of a disconnected graph is the direct sum of the cycle spaces of its components, Proposition 1.5 shows that the dimension of the cycle space of a graph G is given by the formula dim«(G) = e(G) - v(G) + c(G). 1.5. Extremal graphs Proposition 1.5 has the following immediate consequence. Corollary L6. Let G be a graph on n vertices and m edges, where m^n. Then G contains a circuit. 12 J.A. Bondy Corollary 1.6 is a very simple instance of a result in extremal graph theory. It asserts that every graph on л vertices and sufficiently many edges (at least n) contains a circuit. Furthermore, the bound on the number of edges is best possible because there exist graphs on n vertices and л — 1 edges that do not contain circuits (namely trees); these graphs (trees) are referred to as extremal graphs for the property in question (containing a circuit). While a graph on n vertices and at least n edges is guaranteed to contain a circuit, the length of the circuit may take on any value between 1 and n. The following theorem, due to Mantel A907), specifies how many edges are needed to guarantee the existence of a triangle in a simple graph. Theorem 1.7. Let G be a simple graph on n vertices and m edges, where m>n2/4. Then G contains a triangle. Proof (by contradiction). Suppose that G contains no triangle. Then adjacent ver- vertices have disjoint sets of neighbours, so d(u) + d(v) Ц n, for each edge uv ? E. Summing over all edges of G, we have On the other hand, by Chebyshev's inequality and Proposition 1.1, These two inequalities imply that m ^ n2/4, contradicting the hypothesis. ? Equality holds in the above inequalities only if G is regular of degree и/2. It follows readily that the extremal graphs in this case are the complete bipartite graphs К"/2,"/2. Theorem 1.7 is a special case of Turin's Theorem, the cornerstone of extremal graph theory. This topic is the subject of chapter 23 by Bollobis. 1.6. Search trees Theorem 1.3, Corollary 1.6 and Theorem 1.7 assert only that certain types of paths and circuits may be found in graphs with appropriate properties. They do not address the question, of paramount importance in practical applications, of how to find such subgraphs. Of course, an exhaustive search of a finite graph can always, in theory, be completed in finite time. In practice, however, this is not good enough - time is of the essence; to be effective, an algorithm must be efficient. The running time of an algorithm is measured by the total number of basic operations (arithmetic operations, comparisons, and so on) required to implement it, and depends on the size and nature of the input. The complexity of a graph- theoretical algorithm is its running time, in the worst case, on graphs of a given Basic graph theory: Paths and circuits 13 size (meaning, usually, their number of vertices and/or edges). A polynomial-time algorithm is one whose complexity is bounded above by a polynomial in the size of the input graph, an exponential-time algorithm one whose complexity is bounded below by an exponential function in the size of the input graph. Polynomial-time algorithms are regarded as efficient because their running time grows relatively slowly with the size of the input; this means that fairly large graphs (perhaps with several hundred vertices) can be handled effectively. Exponential-time algorithms, on the other hand, may take inordinately long to process graphs of very modest size (say, twenty vertices). Spanning trees provide an efficient way to search graphs, and are the key to many polynomial-time algorithms. A search tree in a connected graph is a spanning tree whose vertex set {va, vt,..., i>n_i} and edge set {ei, ег e*-i} are ordered in such a way that, for each /, 1 < / < n — 1, the subgraph with vertex set {i;0, ub..., vf\ and edge set {e^ej,...,^} is a tree; the vertex uj is the root of the search tree. In other words, a search tree is the growth process of a spanning tree, not just the tree itself. Starting at the root v0, the tree is grown by adding a vertex v/ and edge e/ = ViUj at each stage of the process; we call u; a child of vh and v, the parent of vj, in the tree. In general, there is some freedom as to the choice of vt and ey, but if they are chosen appropriately, important structural information about the graph is encoded in the resulting search tree. The most basic type of tree search, breadth-first search, was developed by Dijkstra A959). A breadth-first search tree is a search tree with vertex set {vo, f i, • •, v"_i} and edge set {ei,e2,...,en-]} where, for each j, 1 </ ^ л - 1, Vj and с; are chosen in such a way that the parent of u, is the vertex v, with smallest possible index i. Such a tree can be grown in linear time. The key property of breadth-first search is that the distance in a breadth-first search tree between its root and any other vertex is the same as their distance in the graph itself. Thus, by growing a breadth-first search tree from each vertex, shortest paths between all pairs of vertices in a graph can be found. In particular, the diameter can be determined. Breadth-first search also enables one to decide easily whether or not a graph is bipartite. Let Г be a breadth-first search tree with root x in a graph G, which we assume to be connected. (If it is not, the procedure may be applied to each component in turn.) Let X be the set of vertices whose distance from x is even, and Y the set of vertices whose distance from x is odd. If no two vertices of X and no two vertices of У are adjacent, (A", Y) is a bipartition of G and so G is bipartite. If, on the other hand, two of these vertices, и and v, are adjacent, consider the шг-path P and ui-path Q in T. Let w denote the first vertex common to P and Q. Then /"[«,»>] and C[i>,w] are paths of the same parity and so, together with the edge uu, form an odd circuit of G. We conclude that G is not bipartite in this case, since a circuit in a bipartite graph alternates between the sets of its bipartition and thus is necessarily even. The above algorithm outputs a bipartition if the input graph is bipartite and an odd circuit if it is not. Thus it supplies, as a byproduct, the following characteriza- characterization of bipartite graphs, due to Konig A916). 14 J.A. Bondy Theorem 1.8. A graph is bipartite if and only if it contains no odd circuit. If a graph is not bipartite, a shortest odd circuit can be found by growing a breadth-first search tree with root x from each vertex x. It is less easy to find a shortest even circuit, if there is one; an algorithm for doing so is described in section 4 (at the end of the discussion of stability number). The above examples illustrate the power of breadth-first search. Another highly effective tree search procedure, depth-first search, was developed by Tarjan A972). A depth-first search tree is a search tree with vertex set {v0, vu..., vn^i] and edge set {e, ,e2,...,en-i} where, for each ;', l^j^n — l,Vj and e, are chosen in such a way that the parent of v, is the vertex v, with largest possible index i. Depth-first search also takes linear time. It can be used to find the blocks and cut vertices of a graph, and has many other important applications. These are described in chapter 28 by Giotschel, and in the book by Aho et al. A974). In applications, the edges of a graph often have associated weights, or costs. An edge-weighted graph is a graph G together with a weight function w that assigns to each edge of G a weight w(e). Usually, the range of w is the set of nonnegative real numbers; in some instances, however, a different choice is appropriate: the set of all real numbers, the set of integers, or the set of integers modulo m, for example. The weight of an edge-weighted graph is the sum of the weights on its edges. An unweighted graph can be regarded as an edge-weighted graph in which each edge has weight one; its weight is then simply its size. In this way, results about graphs can sometimes be generalized to weighted graphs. Dijkstra A959) showed, for instance, not only how to find shortest paths in graphs but, more generally, how to find minimum-weight paths in edge-weighted graphs with nonnegative weights. Most of the theorems to be mentioned in this chapter have proofs that can be adapted fairly easily to yield polynomial-time algorithms. However, there are many basic problems for which polynomial-time algorithms have yet to be found, and indeed might well not exist. In fact, determining which problems are solvable in polynomial time is one of the main preoccupations of theoretical computer scien- scientists. An important class of problems in this regard is the class XSP (standing for nondeterministic polynomial-time). We give here an informal definition; a precise treatment can be found in chapter 29, or in the book by Garey and Johnson A979). A decision problem is a question whose answer is either "yes" or "no"; any object to which the question is addressed is an instance of the problem. A decision problem belongs to the class 9 if there is a polynomial-time algorithm that solves any instance of the problem in polynomial time. A decision problem belongs to the class Jf9 if, given any instance of the problem whose answer is 'yes', there is a certificate validating this fact which can be checked in polynomial time, and one, moreover, whose length is bounded above by a polynomial in the size of the input; such a certificate is said to be succinct. It follows from these definitions that 9 С Л9, since a polynomial-time algorithm is, in itself, a succinct certificate. The problem of determining whether a graph is bipartite belongs to 9 and hence also to Jf9\ likewise, the problem of determining whether a graph is nonbipartite belongs to both 9 and Я9. On the other hand, even though no polynomial-time Basic graph theory: Paths and circuits 15 algorithm is known for determining whether a graph contains a spanning circuit, this problem belongs to Jf9, an appropriate certificate being the spanning circuit itself. Verifying that a graph contains no spanning circuit, by contrast, appears to be much harder; indeed, its status as regards membership in Jf9 is unresolved. As noted above, 9 С Jf9. Whether 9 = Я9 or not is the most fundamental open question in theoretical computer science. The so-called X9-complete prob- problems, which form a subclass of Jf9, are of much interest in this regard. These problems, which include the problem of determining whether a graph contains a spanning circuit, are algorithmically the most difficult in N9, in the sense that if any one of them can be solved in polynomial time, then so can every problem in Jf& (that is, 9 — Л9). Several .AT ^-complete problems will be encountered in this chapter. The Л^-complete problems belong to a larger class of seem- seemingly intractable problems, the class of X9-hard problems. The concept of Jf9- completeness was set on a sound theoretical footing by Cook A971) and further developed by Karp A972). 1.7. Directed graphs A directed graph, or digraph, О is a graph G in which each edge is assigned a direction, one end being designated its tail and the other its head. We call D an orientation of G, and write D:= G. An edge with tail x and head у is denoted by the ordered pair (x,y); we say that x dominates у and write x —»y. In diagrams, the direction of an edge is indicated by an arrow pointing towards the head of the edge. Two or more edges with the same tail and head are multiple edges. A strict digraph is one with neither loops nor multiple edges. The associated digraph D(G) of a graph G is the digraph obtained from G by replacing each edge by two oppositely directed edges with the same ends. An example is the strict complete digraph, the associated digraph D(Kn) of the simple complete graph К". The underlying graph G(D) of a digraph D is the graph obtained from D by ignoring the orientations of its edges. An oriented graph is a digraph whose underlying graph is simple. A tournament is a digraph whose underlying graph is simple and complete. The adjacency matrix A(D) of a digraph D is the matrix (а") whose rows and columns are indexed by the vertices of D, am being the number of edges of D with tail и and head v. Let obea vertex of a digraph D. The outdegree d*D(v) of v in D is the number of edges of D whose tail is u, the indegree d^(v) the number of edges of D whose head is v. A sink is a vertex of outdegree zero, a source a vertex of indegree zero. The analogue for digraphs of Proposition 1.1 asserts that, for any digraph D, A directed walk in a digraph D is a sequence W := (va,ei,v\,...,et,vi), where vo,vu...,vt are vertices of D,eu...,et are edges of D, and u,_i andu< are the tail and head, respectively, of e,, 1 $ i < I. The vertices v0 and vt are the tail and head 16 J.A. Bondy of W; when one wishes to refer to them explicitly, W is described as a (vq, vt)-walk. The notions of directed trail, directed path, and directed circuit are defined in an analogous manner, as are directed girth and directed diameter. A digraph is strong (or strongly connected) if any two vertices x and у are connected by an (x,y)-path. A strong component of a digraph D is a maximal strong subdigraph of D. Graphs can be regarded as a subclass of digraphs, a graph being identified with its associated digraph. This leads to a basic question, one that we shall examine with respect to paths and circuits: which properties of graphs extend to digraphs? Another fundamental question has to do with the relationship between a graph and its orientations: how are the properties of a graph reflected in the properties of its orientations? This latter question was studied by Chva4al and Thomassen A978) with regard to girth and diameter. They established the existence of an integer- valued function / and an orientation function —t such that, for any graph G and any edge e of G that belongs to a circuit of length at most k, the image ~e of e belongs to a directed circuit of length at most f(k) in G. This implies, in particular, that a connected graph with no cut edge has a strongly connected orientation, a result due to Robbins A939). Chvatal and Thomassen A978) obtained a similar but sharper result for the diameter. Theorem 1.9. Let G be a graph of diameter d with no cut edge. Then G admits an orientation of directed diameter at most Id1 + 2d. A digraph is acyclic if it contains no directed circuit. An acyclic tournament is called a transitive tournament, the one of order л being denoted ТТ". The digraph D" obtained from D by contracting each strong component to a single vertex is an acyclic digraph, the condensation of D; if D is a tournament, D* is a transitive tournament. A strong component of D is called maximal if it has indegree zero in D' and minimal if it has outdegree zero in D". An arborescence is an orientation of a tree in which one vertex, called the root, has indegree zero and every other vertex has indegree one. The analogue for digraphs of a breadth-first search tree is a breadth-first search arborescence. Shortest directed paths between pairs of vertices in a digraph can be found efficiently by growing such arborescences. In a strong digraph, a directed odd circuit can also be found in this way, if there is one. Consider a breadth-first search arborescence with root x. Let X be the set of vertices whose distance from x is even, and У the set of vertices whose distance from x is odd. If some edge e joins two vertices in the same set, x is connected to the head у of с by directed paths of both parities. The concatenation of one of these paths with a (j>,i)-path is a directed closed walk of odd length, which necessarily contains a directed odd circuit. On the other hand, if each edge has one end in X and the other end in Y, the digraph is bipartite. Thus a digraph has a directed odd circuit if and only if some strong component is not bipartite. This characterization leads directly to a theorem of Richardson A953) on the existence of kernels in digraphs. A kernel in a digraph D is a set S of pairwise nonadjacent vertices that together dominate every vertex of V \ S. Many digraphs Basic graph theory: Paths and circuits 17 fail to have kernels, the simplest being the directed odd circuits. What Richardson proved is that a digraph without a kernel necessarily contains a directed odd circuit. Theorem 1.10. Let D be a digraph with no directed odd circuit. Then D has a kernel. Proof. By induction on the order of D. If D is strong, then D is bipartite and each class of the bipartition is a kernel of D. If D is not strong, let D] be a maximal strong component of D, with vertex set V\. By the induction hypothesis, D, has a kernel, Si. Let V2 be the set of vertices of D dominated by vertices of St, and define D2 := D \ (V, и V2). Again by induction, D2 has a kernel, S2. The set Si U S2 is a kernel of D. a Kernels originated in the analysis of games on graphs, a kernel representing a set of winning positions. But they have other applications. We refer the reader to Berge A985, chapter 14) for further information. A shortest directed odd circuit is a shortest directed closed odd walk, and such a walk, if one exists, can be found in polynomial time by taking odd powers of the adjacency matrix until a nonzero diagonal entry is encountered. Finding a directed even circuit appears to be a much harder proposition. Friedland A989) gave a simple necessary and sufficient condition in terms of the adjacency matrix for a digraph to contain such a circuit. Theorem 1.11. Let D be a digraph, with adjacency matrix A. Then D has a directed even circuit if and only if per {1 +А)фй<А (I+A), where per denotes the permanent and det the determinant. However, no polynomial-time algorithm has been developed to determine when this condition is satisfied. On the other hand, the problem of finding a directed even circuit in a digraph (posed by D.H. Younger - see Bermond and Thomassen 1981) has not been proved ¦AfS'-complete. Problem L12. Is there a polynomial-time algorithm for finding a directed even circuit in a digraph? Thomassen A993) has described such an algorithm for planar digraphs. Besides being a fundamental question, Problem 1.12 has an intriguing knife-edge quality: the slightly harder question of deciding whether there is a directed odd (or even) circuit through a given edge in a digraph is already Л9 -complete (Thomassen 1985a). Prbblem 1.12 turns out to be equivalent to a question about a special class of digraphs considered by Seymour and Thomassen A987). To subdivide an edge e := xy in a graph is to replace e by a path P := xvy, where v is a new vertex. A subdivision of a graph is any graph derivable from it by recursively subdividing 18 J.A. Bandy ,*>. Basic graph theory: Paths and circuits 1 19 Figure 2. The Koh digraph. edges. Analogous definitions apply to digraphs, the path P being a directed path in this case. Seymour and Thomassen A987) characterized the digraphs with the property that every subdivision contains a directed even circuit. This characteriza- characterization does not, however, lead to a polynomial-time recognition algorithm. Indeed, Seymour and Thomassen showed that the existence of such an algorithm is equiv- equivalent to the existence of a polynomial-time algorithm for finding a directed even circuit in a digraph. Thomassen A992) found a sufficient condition in terms of the minimum indegree and outdegree for the existence of a directed even circuit in a strong digraph. Theorem 1.13. Let D be a strict strong digraph of minimum indegree S~ and minimum outdegree 8*, where 8 > 3 and 8* ^ 3. Then D contains a directed even The bound on the degrees in Theorem 1.13 is sharp. Figure 2 shows a strong 2-diregular digraph on seven vertices without directed even circuits, found by Koh A976). 1.8, Hypergraphs A hypergraph H consists of a set V(H) of elements, called vertices, and a family E(H) of subsets of V(H), called hyperedges (or simply edges, when there is no ambiguity). An example is the Fano hypergraph, shown in fig. 3, which has as vertices and edges the seven points and seven lines of the Fano plane, the finite projective plane PGB,2) (see, for example, Biggs and White 1979). Note that the seven 3-subsets defined by the vertices of the Koh digraph (fig. 2) and their outneighbours constitute the edges of the Fano hypergraph; this is an instance of a connection established by Seymour A974) between strong digraphs without directed even circuits and a certain class of hypergraphs of which the Fano hypergraph is prototypical. A vertex и and edge e of a hypergraph are incident if v e e. The incidence graph of a hypergraph H is the bipartite graph with bipartition (V(H),E(H)) in which V={i,2,3,4,5,6,7} E= {124,235,346,457, 561,672,713} Figure 3. The Fano hypergraph. Figure 4. The Heawood graph. v e V(H) and e ? E(H) are adjacent if and only if they are incident in H. The incidence graph of the Fano hypergraph is a 3-regular graph on fourteen vertices known as the Heawood graph, shown in fig. 4. With each hypergraph, we may thus associate a bipartite graph. Conversely, to each bipartite graph G(X, Y), there corresponds a hypergraph Я whose vertex set is X and whose hyperedges are the sets of neighbours of the vertices of Y. In this way, we can recover a hypergraph from its incidence graph, so the two structures are, in a sense, one and the same. Many other hypergraphs of interest can be associated with a graph G. We have already encountered one, the cycle space ^(G), which may be regarded as the hypergraph whose hyperedges are the edge sets of the even subgraphs of G. Retaining only the minimal non-null elements of ^(G), we obtain the hypergraph whose hyperedges are the edge sets of the circuits of G. This hypergraph has two special properties: (a) no proper subset of a hyperedge is a hyperedge, and (b) if C\ and C2 are hyperedges and e is an element of C\ П Сг, then {C\ и Сг) \ е contains a hyperedge. A hypergraph with property (a) is termed a clutter, one with properties (a) and (b) a matroid. The matroid defined by the circuits of a graph G is called the cycle matroid of G. Although they are a substantial abstraction of graphs, matroids capture perfectly certain graph-theoretical concepts and properties; indeed, they are the appropriate framework for the study of graph minors and for the treatment of a number of significant questions about circuits, forests and spanning trees. They are also of 20 J.A. Bondy fundamental importance in the related field of combinatorial optimization. Their properties are discussed in chapters 9-11 and, more fully, in the book by Welsh A976). Hypergraphs appear in various guises throughout combinatorics. They are treated in several chapters of this handbook, in particular in chapter 7, as well as in the book by Berge A989). 2. Hamilton paths and circuits in graphs 2.1. Dirac's theorem For a simple graph G, the minimum degree S is a parameter of some importance. The larger it is, as a function of n, the more likely it is that G contains a particular subgraph. For instance, Theorem 1.3(ii) implies that if S > 2 then G contains a circuit, and it follows from Proposition 1.1 and Theorem 1.7 that if S > n/2 then G contains a triangle; yet another illustration is provided by Theorem 1.13. The theorem that initiated the study of long circuits (Theorem 2.1 below) is of this type. A path or circuit that includes every vertex of the graph is called a Hamilton path or circuit. A hamiltonian graph is one that contains a Hamilton circuit, a traceable graph one that contains a Hamilton path. As we noted in section 1, the problem of determining whether a graph contains a Hamilton circuit is JV<?>-complete. The more general problem of finding a minimum-weight Hamilton circuit in an edge- weighted complete graph is also JV3>-complete. Known as the Travelling Salesman Problem, this latter question has been the subject of much study. Its many aspects are surveyed in chapters 28 and 35, and in the book edited by Lawler et al. A985). Whether it is Jf 9-hard to determine the parity of the number of Hamilton circuits, a question raised by K.A. Berman (personal communication 1986b), is not known. Dirac A952) determined how large the minimum degree must be to guarantee the existence of a Hamilton circuit. Theorem 2.1 (Dirac's Theorem). Let G be a simple graph of minimum degree S on n vertices, where S ^ n/2 and n ^ 3. Then G contains a Hamilton circuit. We present three proofs of this fundamental result. All are based on an ob- observation that we shall refer to as the Lollipop Lemma B.2). An (x,y)-lollipop is a graph CuP, where С is a circuit and P an лсу-path such that СПР = {y); lollipops have also been called loops and lassos. Let С be a circuit in a graph G, with a specified orientation, and let x be a vertex of C. The predecessor of x on С is denoted by x~, the successor of x on С by x*. This notation is extended to a set S of vertices of С in the natural way: 5-:={л:-|*еХ} and S* := {x*\x e S}. Lemma Z2 (The Lollipop Lemma). Let С UP bean (x,y)-lollipop in a graph G, where С is a circuit of length I and P a path of length m. Then G contains the xy~- Basic graph theory: Paths and circuits ¦S Figure 5. Two paths in a lollipop. 21 path PC\y,y] and the xy*-path P С \у,у*}, both of length l + m-\. In particular, if С is a longest circuit of G and P is nontrivial, x is nonadjacent to both y~ and У*- The Lollipop Lemma B.2) is illustrated in fig. 5. Simple though it is, this lemma is the basis of many theorems on paths and circuits. We shall appeal to it frequently, often without explicit reference. The first proof that we give of Dirac's Theorem B.1) is essentially the one given by Dirac himself. Proof 1 (by choosing a longest circuit). Let С be a longest circuit in G, of length t. By Theorem 1.3(ii), ( > 6 + 1. If С is a Hamilton circuit, there is nothing to prove, so suppose that G \ С ф 0. Let С и P be an (x,)>)-lollipop, where P is as long as possible. Let m be the length of P. Note that since each vertex of G \ С is adjacent to some vertex of C, and so m > 1. Each vertex of P is a potential neighbour of x. On the other hand, no vertex of С \у whose distance from у along С is m or less can be adjacent to x; and of the remaining vertices of C, no two consecutive ones can be adjacent to x. We deduce that ... t -2m I n d(x) s$ m +- —-— = - < - $ 8, a contradiction. ? The second proof of Dirac's Theorem B.1) is due to Newman A958). Proof 2 (by choosing a longest path). Let P be a longest path in G, of length I. We first show that G has a circuit of length l + l.It the ends, x and y, of P are adjacent, С := P +xy is such a circuit. So we may assume that x and у are not adjacent. By the choice of P, all the neighbours of x and у lie on P. Set P :=vovi--vt, where v0 :=* and vt :=y, and define X := {v<: vovM 6 ?}, У := fa: iw e ?}. 22 I.A. Bondy We shall prove that X n Y ф 0. Since 5 > л/2, and, since >¦ ? XuY, \XUY\il $ Therefore Let vk e А"ПУ. Then is a circuit of length I + 1. We now show that С is a Hamilton circuit of G. If not, let С и Р be a lollipop, where P has length m and, as in Proof 1, m > 1. By the Lollipop Lemma B.2), G contains a path of length ? + m, contradicting the choice of P. Therefore С is indeed a Hamilton circuit of G. D The third proof that we give of Dirac's Theorem, due to Bondy A981), incor- incorporates elements of each of the other two. Proof 3. Let С be a longest circuit in G. If С is a Hamilton circuit, there is nothing to prove, so suppose that G\C^0 and let CUP be an (x,j>)-lollipop. Set Vi:=V[C), V2:=V(P)\y, Vf-V(G)\V(CuP), and let d, (x) and di(y*) denote the numbers of neighbours of x and y*, respectively, in V}, i = 1,2,3. Since С is a longest circuit, we deduce that (i) x and y* cannot be adjacent to consecutive vertices v and v*, respectively, onC; (ii) y* cannot be adjacent to any vertex of V3; (iii) x and y* cannot be adjacent to a common vertex of V$. By (i), by (ii), and, by (iii), d,{x Since di(x) < |V2| - 1, Basic graph theory: Paths and circuits 23 we have \V2\ + Щ - 1 = n - contradicting the hypothesis. Thus С is indeed a Hamilton circuit of G. D No inductive proof of Dirac's Theorem B.1) is known. A false one was concocted by Woodall A975) in order to illustrate the potential pitfalls of this fundamental technique. By the simple idea of transforming one problem into another, further results can be derived very easily. We give one small illustration; others can be found in chapter 29 by Shmoys and Tardos. Corollary 23. Let Gbea simple graph of minimum degree S on n vertices, where — l)/2. Then G contains a Hamilton path. Proof. For л = 1, the result is trivial. For л > 2, we form the graph H:— G + v. This graph H has n +1 vertices and minimum degree at least (n +1)/2. By Dirac's Theorem B.1), Я contains a Hamilton circuit C. The subgraph С \ v is a Hamilton path of G. a 2.2. Generalizations of Dirac's theorem Dirac's Theorem B.1) is important because it is amenable to generalization in a great variety of ways. To start with, the hypothesis can be weakened. Proof 2 does not use the full strength of the hypothesis 5 J: n/2, but just the weaker condition that the ends x and у of a longest path satisfy the inequality d(x) + d(y) > n. Moreover, this latter condition is applied only to nonadjacent vertices x and y. Thus the very same proof yields the following stronger theorem, due to Ore A960). Theorem 2.4 (Ore's Theorem). Let G be a simple graph on n vertices, where n > 3, in which the degree sum of any two nonadjacent vertices is at least n. Then G contains a Hamilton circuit. In fact, if one examines the proof more carefully still, one sees that it is based on the following observation. Proposition 2.5. Let Gbe a simple graph on n vertices, where n > 3, and let x and у be nonadjacent vertices of G with degree sum at least n. If G + xy is hamiltonian, then so is G. This observation leads naturally to the definition of a closure operation on graphs. The closure of a graph Сопл vertices is the graph derived from G by recursively joining pairs of nonadjacent vertices having degree sum at least n. Repeated application of Proposition 2.5 yields the following result of Bondy and Chvatal A976). 24 J.A. Bondy Lemma 2.6 (The Closure Lemma). A simple graph G is hamiltonian if and only if its closure is hamiltonian. In particular, a graph is hamiltonian if its closure is complete: the graphs sat- satisfying the hypothesis of Dirac's Theorem B.1) are hamiltonian for this reason. Chviital A972) found a wider class of graphs defined in terms of their degree se- sequences (the widest, in a certain sense) whose closures are complete and which are consequently hamiltonian. Theorem 2.7. Let G be a simple graph on n vertices with degree sequence (di,<fe,• ¦• idn), where п^Ъ and dt < di < ¦ • • < dn. If there is no value of к ^ (n — l)/2 such that dk ^k and dn^k <n-k, then G contains a Hamilton circuit. Proof. We shall show that the closure of G is complete; the conclusion will then follow directly from the Closure Lemma B.6). Suppose, to the contrary, that this is not so. Let H be the closure of G. Then the degree sum of any two nonadjacent vertices of H is at most n — 1. Let x and у be two such vertices of И whose degree sum is maximum. Without loss of generality, we may assume that dH(x) ^ dH(y). Set dH(x) := k. Then k^(n- l)/2 and dH{y) K.n-k-1. Denote by X the set of vertices nonadjacent to у in H. Then |A"| = n — 1 - dH(y) 2= k. Also, by the choice of x and y, dG(v) < d,i(v) < к for all v e X. Similarly, if Y denotes the set of vertices that are nonadjacent to x in H, we have \Y\ — n - к - 1 and d(;(v) ^d,,(vLn-k - 1 for all v e Y. Thus G has at least к vertices of degree at most к (namely those in the set A") and at least n - к vertices of degree at most n — k — \ (namely those in the set Y и {х}). This contradicts the hypothesis on G. We deduce that the closure of G is indeed complete, as claimed. ? Tian and Shi A986) observed that the Closure Lemma B.6) can also be used to give an easy proof of a generalization of Ore's Theorem B.4) due to Fan A984): ;/ G is a simple graph on n vertices, where n~^% in which no two vertices of degree less than n/2 have a common neighbour, then G contains a Hamilton circuit. Shi A992) and Bollobds and Brightwell A993) gave the following elegant gen- generalization of Dirac's Theorem B.1). Theorem 2.8. Let G be a simple graph on n vertices, and let S denote the set of vertices of degree at least n/2 in G. If \S\ > 3, G has a circuit that includes every vertex of S. Proof. Let С be a circuit that includes as many vertices of 5 as possible. Suppose that 5 \ V(C) Ф 0, and let С UP be an OE,;y)-lollipop, where x <E S. Note that С includes at least two vertices of S because any two nonadjacent vertices of 5 lie in a 4-circuit of G. Let z be the first vertex of 5 following у on C. Then, as in Proof 3 of Dirac's Theorem B.1), the choice of С implies that d{x) + d{z) ^ л - 1, a contradiction. D Another way in which Dirac's Theorem B.1) can be strengthened is by refining its conclusion. Corollary 2.10 below is such a result. A graph on n vertices is Basic graph theory: Paths and circuits 25 pancyclic if it contains circuits of every length 1,3 < t $ и. In particular, a pancyclic graph is hamiltonian. The following theorem of Bondy A971a) gives a condition under which the converse holds. The proof presented here is due to C. Thomassen (see Bollobas 1978). Theorem 2.9. Let G be a simple hamiltonian graph on n vertices and at least л2/4 edges. Then either G is pancyclic or n is even and G = Кп1г^/ъ Proof (by induction). There is nothing to prove when n = 3, so assume that n^4. Suppose, first, that G has a circuit of length л - 1, Let в := V{G) \ V(C). If d(v) $ (л - 1)/2, then By the induction hypothesis, G \ v is pancyclic. Since G is hamiltonian, by hypoth- hypothesis, G is pancyclic too. If d(v) > (n -1)/2, there exists for each t, 3 < t ^ л, an index / such that both vv; and vul+t-2 are edges of G, and G contains the circuit vViC[vi,ul+i_2]u<tf-2V, of length I. Thus G is pancyclic in this case too. Suppose, now, that G has no circuit of length n -1. Let v\ v2 ¦ ¦ ¦ vnvl be a Hamil- Hamilton circuit of G. Then, for alii,/ such that 1 < ;, / < я and/ ф\ — l,i, at most one of the pairs u,u; and i>,+ii>,+2 can be an edge of G. Thus dfa) + d(v,+\) «л. Summing over all i, 1 < i Ц n, we have whence Equality holds only if л is even and, for all i,j such that 1 ^ i, j <, n and j^i- 1, i, exactly one of the pairs vtv, and d,+iU;+2 is an edge of G. It follows easily that G K G = K n/2j,/2 in this case. Q Corollary 2.10. Let G be a simple graph of minimum degree Sonn vertices, where S J; л/2. Then either G is pancyclic or n is even and G — Kn/2],,/2- Corollary 2.10 was refined substantially by Amar et al. A991), who proved that a simple hamiltonian graph of minimum degree S on n vertices, where S > 2n/5 and n is sufficiently large, is either pancyclic or bipartite. Nash-Williams A971a) strengthened the conclusion of Dirac's Theorem B.1) in a very different manner. 26 J.A. Bandy Theorem 2.11. Let Gbea simple graph of minimum degree Sonn vertices, where S > л/2 and np3. Then G contains at least \cn\ edge-disjoint Hamilton circuits, where с = 5/224 и 0.0223. Weakening its hypothesis and strengthening its conclusion are two ways to gen- generalize a theorem. A more common way is simply to extend the domain of the hypothesis, including the theorem as a special case. There are many such general- generalizations of Dirac's Theorem B.1). We begin with one due to P6sa A963). A path system is a graph each of whose components is a path. Theorem 2.12. Let s be a nonnegative integer, G a simple graph of minimum degree S on n vertices, where 8>(n + s)/2 and n ^ 3, and S a set of s edges of G that induce a path system. Then G contains a Hamilton circuit that includes every edge of S. Proof (by considering a maximal counterexample). Suppose the theorem is false for some value of n, and let G be a maximal graph on л vertices satisfying the hypotheses but not the conclusion (for some set S of edges). Since a complete graph clearly satisfies the conclusion (for any set S), G is not complete. Let x and у be two nonadjacent vertices of G. Then G + xy also satisfies the hypotheses of the theorem (for the set 5). By the maximality of G, there is a Hamilton circuit С in G + xy that includes S. Because G does not contain such a circuit, xy e E{C). Let P ¦= C\xy. Then P is a Hamilton path in G that connects x and у and includes S. Let P := v, v2 ¦ ¦ ¦ vn, where vi := x and и" ;= у. A counting argument similar to the one used in Proof 2 of Dirac's Theorem B.1) shows that, for some k, 1 < к ^ "-I, -™*+i 6 E, vky e E and vtvktl $ S. But now P[vuvk]vkvn(p~[vn:vk^]vMvi is a Hamilton circuit in G that includes S, contradicting our initial supposition and establishing the theorem, a Note that the above proof, restricted to the case s = 0, closely resembles Proof 2 of Dirac's Theorem B.1) but is more succinct. In the case j = 1, a slightly stronger conclusion can be deduced. A graph is Hamilton-connected if any two of its vertices are connected by a Hamilton path. Implicit in the work of Erdos and Gallai A959, Lemma 1.6) is the following theorem. Corollary 2.13. Let Gbea simple graph of minimum degree S on n vertices, where S^( 1)/2 and n 3= 3. Then G is Hamilton-connected. Proof. That any two adjacent vertices in G are connected by a Hamilton path follows directly from Theorem 2.12. For a nonadjacent pair, it suffices to add an edge e joining them and apply Theorem 2.12 to the graph G + e and the set S := {e}. a A Hamilton circuit is one that is as long as possible, passing through each vertex of the graph. Dirac's Theorem B.1) has been generalized to results asserting the existence of long (but not necessarily Hamilton) circuits. We mention two instances, the first due to Egawa and Miyamoto A989) and BoUobds and Brightwell A993)! the second to Dirac himself A952). I Basic graph theory: Paths and circuits 27 Theorem 2.14. Let к be a positive integer and G a simple graph of minimum degree S on n vertices, where S > n/(k + 1) and п^Ъ. Then G contains a circuit of length at least njk. Theorem 2.15. Let G be a simple nonseparable graph of minimum degree S on n vertices, where л > 3. Then G contains either a circuit of length at least 25 or a Hamilton circuit. Strictly speaking, Theorem 2.15 is not a generalization of Dirac's Theorem B.1) because of the additional requirement that G be nonseparable. However, the latter property is an easy consequence of the hypothesis of Dirac's Theorem B.1). Thus we may indeed regard the theorem as a generalization. A similar comment applies to the following result of Bondy and Nash-Williams (see Nash-Williams 1971a, p. 159), where the degree condition of Dirac's Theorem B.1) is relaxed considerably. This result is a useful adjunct to the Hopping Lemma F.7), a powerful proof technique developed by Woodall A973), and will be employed in section 6. Theorem 2.16. Let G be a simple nonseparable graph of minimum degree Sonn vertices, where S > (n +2)/3 and n > 3, and let С be a longest circuit of G. Then no two vertices of G\C are adjacent. Theorems 2.15 and 2.16 can both be derived by the longest-circuit technique, the strategy being to examine the structure of the components of G \ C, where С is a longest circuit. A proof of Theorem 2.15 will be given in section 4 (see Theorem 4.11). A Hamilton circuit can also be viewed as a spanning walk that is as short as possible, passing through each vertex just once. Jackson and Wormald A990a) and Pruesse A990) generalized Dirac's Theorem B.1) to spanning walks that pass through each vertex no more than к times; such walks are called k-walks. Theorem 2.17. Let к be a positive integer and G a simple connected graph of minimum degree S on n vertices, where S ^ n/(k +1) and n^3. Then G has a k-watk. A closely related concept is that of a k-tree, a spanning tree in which each vertex is of degree at most k; 2-trees are thus Hamilton paths. It is easy to see that a Ачгее admits a it-walk in which each edge of the tree is traversed twice. Jackson and Wormald A990a) showed, conversely, that a graph which admits a fc-walk necessarily contains a (k+ l)-tree. Theorem 2.17 thus implies that, for к 5= 2, a simple connected graph of minimum degree S on n vertices, where 5 > n/k and n > 3, has a jfc-tree. Win A975) obtained a slightly sharper bound on the minimum degree. Theorem 2.18. Let к be an integer, к ~Z 2, and G a simple connected graph of minimum degree S on n vertices, where S > (л — l)/k. Then G contains a k-tree. Finally, we turn to digraphs and another theorem of Nash-Williams A969). 28 J.A. Bandy Theorem 2.19, Let D be a strict digraph on n vertices with minimum indegree 8~ and minimum outdegree 8*, where min{S~, 5+} > nji. Then D contains a directed Hamilton circuit. This theorem, too, implies Dirac's Theorem B.1), since if a graph G satisfies the hypothesis of Dirac's Theorem B.1), its associated digraph D(G) satisfies the hypothesis of Theorem 2.19. We defer a proof to section 3 (see Meyniel's Theorem, 3.11), observing only that the proof techniques we have described thus far fail for digraphs. The above examples serve to illustrate not only the central role of Dirac's Theorem B.1) in the study of circuits in graphs but also, more importantly, the process of generalization in mathematics. They can be thought of as basic ele- elements in an ever-growing structure of generalizations of Dirac's Theorem B.1). And, just as they generalize Dirac's Theorem B.1), so they too are susceptible to generalization; indeed. Corollary 2.3 (same proof), Corollary 2.10 (similar proof), Theorem 2.12 (same proof), Corollary 2.13 (see Ore 1963), Theorem 2.14 (see Egawa and Miyamoto 1989, or Bollobis and Brightwell, 1993), Theorem 2.15 (Theorem 4.11), Theorem 2.16 (Theorem 4.23, case к — 2), Theorem 2.17 (Theo- (Theorem 4.26), Theorem 2.18 (Theorem 4.27) and Theorem 2.19 (Meyniel's Theorem, 3.11) all admit generalizations of Ore type. Many other generalizations of Dirac's Theorem B.1) can be found in the litera- literature; we shall encounter some in later sections. Surveys on hamiltonian graphs ap- appear periodically. Those by Nash-Williams A975), Lesniak-Foster A977), Bermond A978b), Chvatal A985) and Gould A991) represent a variety of viewpoints on the topic. 3. Hamilton paths and circuits in digraphs 3.1. Redei's theorem In this section, we consider Hamilton paths and circuits in digraphs. The central result here, playing the analogous role to Dirac's Theorem B.1), is a theorem on tournaments due to Redei A934). Theorem 3.1 (Redei's Theorem). Every tournament contains a directed Hamilton path. This theorem is an immediate consequence of the following lemma, the basic idea of which is due to D. Konig and P. Veress (see Redei 1934). Lemma 3.2. Let D be a strict digraph, P an {x,y)-path in D of length I, and veV(D)\V(P). Then (i) dP(v) < I + 2 if there is no (x,y)-path P' in D such that V(P') = V(P) и {v}; (ii) dp(v) < ( if P is a longest directed path in D. I Basic graph theory: Paths and circuits 29 Proof, (i) Let P := (v0,Vj,...,vt), where v0 := x and v, := y, and set X^{v,eV{P)\vo: (v,v,)eE), Y:={i>,eV(P)\Uo: (Vi.uv)eE}. Then XuYQ{vi,V2,...,v,} and XnY = t, for if v, e XnY, the (*,y)-path /" := (va,v\,...,v,-i, v,uh ...,иг) contradicts the hypothesis on P. Thus (ii) If P is a longest directed path in D, neither (v,v0) nor (vt,v) can be an edge of D, and the above argument yields Proof of Theorem 3.1. Let Г be a tournament and P a longest directed path in Г, of length I. If P is not a Hamilton path of T, let v e V(T) \ V(P). Since T is a tournament, dP(v) = t + \. On the other hand, by Lemma 3.2, dr{v) ^ t, a contradiction. Thus P is, indeed, a Hamilton path of T. ? 5.2 Generalizations of Redei's theorem Redei's Theorem C.1), like Dirac's Theorem B.1), admits a number of interesting generalizations. Thomassen A982), for instance, refined it by imposing a rather natural degree condition on the ends of the Hamilton path. Theorem 33. Every tournament contains a directed Hamilton path whose tail is a vertex of maximum outdegree and whose head is a vertex of maximum indegree. Another generalization is a theorem of Redei A934) on the parity of the number of directed Hamilton paths; it was from this result that Redei's Theorem C.1) was originally deduced. Theorem 3.4. Every tournament contains an odd number of directed Hamilton paths. Theorem 3.4 is established by means of a proof technique known as inclusion- exclusion, an inversion formula with applications throughout mathematics. The following version of the formula suffices for our purpose; more general versions are described in chapter 21 by Gessel and Stanley. We omit the proof. Formula 3.5 (Inclusion-Exclusion). Let Z be a finite set and f: 2Z —t R a real- valued function defined on the subsets of Z. Define the function g: 2Z -» R by J.A. Bondy 30 Then If Д is a strict digraph with vertex set V := {1,2,.. ,n) and edge set E, and if ¦л- is a permutation of V, the subset Е" of E defined by Е":=Еп{Aг@,1г<1 + 1)): j = 1,2,...,и - 1} induces a digraph each of whose components is a directed path. Such a digraph we call a directed-path system. Proposition 3.6. Let D be a strict digraph with vertex set V := {l,2,...,n} and edge set E. Denote by П the set of permutations of V and by Ж the set of directed Hamilton paths of D. For each subset X of E, define /(.X) :=|{f 6 П: X = E*}\ and h(X) ¦-\{H e Ж: X С E(H)}\. Then f(X) = h(X) (mod 2). Proof. For each subset A" of E, define g(X) := | {it e П: X С ?,,} |. Then XCYCE and so, by the Inclusion-Exclusion Formula C.5), Observe that g(Y) = r! if and only if the spanning subdigraph of D with edge set У is a directed-path system with r components. Thus g(Y) is odd if and only if У induces a directed Hamilton path H of D, and f(X)= (-I)"-1*1 = AW (mod 2). n *: XCE(H)) Proof of Theorem 3.4. The theorem is valid for transitive tournaments, each of which has precisely one directed Hamilton path. Since any tournament T on n vertices can be derived from the transitive tournament ТТ" by reorienting appro- appropriate edges, it suffices to prove that the parity of h(T), the number of directed Hamilton paths in T, is unaltered by the reorientation of any one edge e. Taking X := {e} in Proposition 3.6, we have /(«)=*(*) (mod 2). Thus, if V denotes the tournament derived from T by reorienting e, h(T')=h(T)+f(e)-h(e)=h{T) (mod 2). ? Bask graph theory: Paths and circuits 31 A third generalization of Redei's Theorem C.1) by Thomason A986), asserting the existence in all sufficiently large tournaments of oriented Hamilton paths of every type (not just directed Hamilton paths). The following definition makes this notion precise. Let О be a digraph, and let P := voei u, ¦ • ¦ e,u< be a (not necessarily directed) I path in D. The type of P is the sequence («i, «2,..., «Д where if c, has head u(_b if e, has head v,. The type of a circuit v\e\ ¦¦¦ vte{v^ is defined similarly. A directed path or circuit is thus one of type (+,+ +). Theorem 3.7. Let T be a tournament on n vertices, where n > 2128. Then T con- contains a Hamilton circuit of each type except, possibly, the directed Hamilton circuit. In particular, T contains a Hamilton path of each type. An analogous generalization of Theorem 3.4 was obtained by Forcade A973), who discovered the remarkable fact that the parity of the number of Hamilton paths of any type in a tournament is independent of the tournament, depending only on the path type. Perhaps more surprising still is the following beautiful corollary of Forcade's theorem. Theorem 3.8. Let T be a tournament of order 2". Then T contains an odd number of Hamilton paths of each type. Excluding the directed Hamilton circuit in Theorem 3.7 is essential; the tran- transitive tournament, for instance, contains no directed circuits whatsoever. Indeed, an obvious necessary condition for the existence of a directed Hamilton circuit in a digraph is that it be strong. Camion A959) showed that for tournaments this condition is also sufficient. Theorem 3.9 (Camion's Theorem). Every strong tournament contains a directed Hamilton circuit. Camion's Theorem C.9) is yet another generalization of Redei's Theorem C.1). To see this, one can use a construction similar to that employed to deduce Corol- Corollary 2.3 from Dirac's Theorem B.1). Alternatively, one can apply Camion's Theo- Theorem C.9) to the strong components of the tournament, thereby obtaining a directed Hamilton path in each, and then piece these paths together to form a directed Hamilton path in the entire tournament. Camion's Theorem C.9) is proved by means of a longest-circuit technique. The following simple lemma is the basis of this and other theorems on directed circuits in strong digraphs. Let D be a digraph, С a subgraph of D, and A" and У sets of vertices of D. A C-bypass is a directed path of length at least two whose head and tail lie in С and whose internal vertices lie in D \ C. An (A", Y)-path is a directed path whose tail lies in A" and whose head lies in У. 32 J.A. Bandy Lemma 3.10 (The Bypass Lemma). Let D be a strong nonseparable digraph, and let С be a nontrivial proper subgraph ofD. Then D contains a C-bypass. Proof. Since D is nonseparable, there is a path in D of length at least two whose tail x and head у belong to С and whose internal vertices belong to D \ C. Among all such paths, we choose one in which the number of edges directed the wrong way (that is, towards x) is as small as possible. We shall show that this path P is a C-bypass. Assume the contrary, and let (u,v) be an edge of P directed towards x. Since D is strong, there exist in D a (C, u)-path Pu and a (v, C)-path Pv. It cannot be the case that the tail of Pu is у and the head of Pv is x, since then the (y,j:)-walk Pa(u,v)Pv would contain a C-bypass, contradicting the choice of P. Without loss of generality, therefore, we may assume that the tail of Pu is г, where z ф у. But now the zy-walk PuP[u,y] contains a гу-path that contradicts the choice of P. Thus P is, indeed, a C-bypass. ? Proof of Theorem 3.9. Let T be a strong tournament and С a longest directed circuit in T. If С is not a Hamilton circuit, T contains a C-bypass by the Bypass Lemma C.10). We choose such a path P that the distance along С from its tail x to its head у is as small as possible. By the choice of C, this distance, the length of C[*,y], is no less than the length of P. Let и and v be internal vertices of С[л,>] and P, respectively. Since T is a tournament, one of these vertices dominates the other. If и dominates v, the («,>)-path (u,v)P[v,y\ contradicts the choice of P. If, on the other hand, v dominates u, the (x,u)-path P[x,v](v,u) contradicts the choice of P. We conclude that С is, indeed, a directed Hamilton circuit of T. ? Moon A968, p. 6) strengthened the conclusion of Camion's Theorem C.9) by showing that every strong tournament is vertex pancyclic: each vertex lies in a directed circuit of every length. This can be proved easily using the Bypass Lemma C.10) (see Bondy 1977). The Bypass Lemma C.10) is also effective in establishing a far-reaching simultaneous generalization of Ore's Theorem B.4), Theorem 2.19 and Camion's Theorem C.9), due to Meyniel A973). The proof we present is by Bondy and Thomassen A977). ' Theorem 3.11 (Meyniel's Theorem). Let D be a strict strong digraph on n vertices, where n^l, in which the degree sum of any two nonadjacent vertices is at least 2n — 1. Then D contains a directed Hamilton circuit. Proof. The degree condition implies that D is nonseparable. Let С := (vi, иг, -.., V/,v\) be a longest directed circuit in D. If С is not a Hamilton circuit, there is a C-bypass in D by the Bypass Lemma C.10). As in the proof of Camion's Theorem C.9), we choose such a path P that the distance along С from its tail x to its head V is as small as possible. Let Vf.= V(P)\{x,y}, Vy V4:=V(D)\(V,Ul/2UVy. C.1) C.2) Basic graph theory: Paths and circuits 33 By the definition of a C-bypass, V, ф 0, and by the choice of C, V2 -ф 0. Let u e V, and v e Vi, and denote by d,(u) and dL(v) the numbers of neighbours of и and v, respectively, in V,, i = 1,2,3,4. Then By the choice of P, и and v are nonadjacent; moreover, d,(u)=0 and d2(«) = 0. Also by the choice of P, there is no directed path (u, w, v) or (v, w,u) with w e V4, and so Finally, by Lemma 3.2 and the choice of C, <*з(и)<|1'з| + 1. Denote by P' a longest (y,*)-path in D such that Vj С V(P') С V2 U Vy Let V^ := V2 \ V(P') and V^ := V(P'), and denote by d[(u) and dj(ti) the numbers of neighbours of и and v, respectively, in v;,i = 2,3. By the choice of C, V2 ф 0. For 1-2 and the latter inequality following from Lemma 3.2 and the choice of P'. Summing the above inequalities yields d(u) + d(v) = d, (u) + d, (u) + d2(u) + d3(M) + d^(v) + d'3(v) + d,(u) + dt(v) | + 2|V2 This contradicts the hypothesis and establishes the theorem. ? 4. Fundamental parameters In this section, we introduce three important measures of the complexity of a graph: the connectivity, the stability number, and the chromatic number. These parameters are discussed in detail in chapters 2 and 4. Here we highlight their relationship to paths and circuits. We also introduce the edge analogues of the above concepts: the edge connectivity, the matching number, and the edge chromatic number, as well as one parameter of particular relevance to paths and circuits, the toughness. 34 J.A. Bondy 4.1. Connectivity and edge connectivity A connected graph is, by definition, one in which any two vertices are linked by a path. Alternatively, a connected graph can be regarded as one whose vertex set admits no partition into two proper subsets, where vertices in different subsets are nonadjacent. These two viewpoints lead to two different ways of measuring the degree of connectedness of a graph. We denote a graph G with two specified vertices x and у by G(x,y). The mem- members of a collection of *}»-paths in a graph G{x,y) are edge-disjoint if no two have an edge in common, and intemally-disjoint if no two have an internal vertex in common. A graph G on at least two vertices is k-edge-connected if any two ver- vertices are connected by at least к edge-disjoint paths, and k-connected if any two vertices are connected by at least к intemally-disjoint paths; a graph on one vertex is denned to be both /c-edge-connected and ^-connected for к = 0,1, but not for к > 2. Thus every graph is 0-connected, a graph is l-connected if and only if it is connected, and a loopless graph with at least two edges is 2-connected if and only if it is nonseparable. Also, since intemally-disjoint paths are edge-disjoint, jfc-connected graphs are /c-edge-connected. Analogous definitions apply to digraphs. A digraph D is strongly k-edge- connected if any two vertices и and и are connected by at least к edge-disjoint (u,u)-paths, and strongly k-connected or k-strong if any two vertices и and v are connected by at least к intemally-disjoint (u,u)-paths. The edge connectivity of a graph G is the greatest integer к for which G is k- edge-connected, the connectivity the greatest integer к for which G is fc-connected. Likewise, in a digraph D, the strong connectivity is the greatest integer к for which D is Л-strong, and the strong edge connectivity is the greatest integer к for which D is strongly /c-edge-connected. The edge connectivity of G is denoted by k'(G), the connectivity of G by k(G), the strong edge connectivity of D by k'(D) and the strong connectivity of D by k(D). These parameters can be computed in polynomial time (see chapter 2). If A" and У are sets of vertices in a graph G, the set of edges of G with one end in A" and the other end in У is denoted by [A", У]. When Xu Y is a partition of V(G), the set [X, Y] is called an edge cut of G; if X, Y ф 0, the edge cut [X, У] is nontrivial; if дг е A" and у е У, it separates x and y. The edge cut [X, Y\ is also called the coboundary of X (or of У). Every nonempty edge cut is a disjoint union of minimal nonempty edge cuts, or bonds. In a connected graph G, a set S of edges is a bond if and only if G \ S has exactly two components. The edge cuts of a graph G form a vector space 38(G) over GFB) called the bond space of G. The bond space and cycle space are orthogonal complements in the edge space. Because of this relationship, edge cuts are sometimes called cocycles and bonds cocircuits. Edge cuts are also referred to as cuts or cutsets. Analogously, if X U S и У is a partition of V, where X, Y ф 0 and no edge of G has one end in A" and the other end in У, the set S is called a vertex cut of G; thus a set S of vertices in a graph G is a vertex cut if and only it G\S is disconnected. If x e X and у е У, we say that the vertex cut S separates x and y; Basic graph theory: Paths and circuits 35 note that only nonadjacent vertices are separated by vertex cuts. Vertex cuts are also called articulation sets. An important and extremely useful theorem due to Menger A927) links these concepts. Theorem 4.1 (Menger's Theorem). - Edge version: Let G(x,y) be a graph. Then the maximum number of edge-disjoint xy-paths in G is equal to the minimum number of edges in an edge cut of G sepa- separating x and y. - Vertex version: Let G(x,y) be a graph, where x and у are nonadjacent vertices of G. Then the maximum number of internally-disjoint xy-paths in G is equal to the minimum number of vertices in a vertex cut of G separating x and y. There is a corresponding version of Menger's Theorem D.1) for directed paths in digraphs. Proofs of both versions are given in chapter 2: Connectivity and Network Flows. Menger's Theorem D.1) is the standard tool for dealing with questions involving connectivity. It is frequently used in the following form. Lemma 42 (The Fan Lemma). Let G be a k-connected graph, where к > 1, let x be a vertex of G, and let Y be a set of at least к vertices of G, where x & Y. Then there exist distinct vertices Ул,Уг,--->Ук '« У and internally-disjoint paths Р\,Рг,---,Рь such that (i) Pi is an xyrpath, 1 ^ i ^ k, and (ii) V{Pt) П У = {у,}, 1 <,'<*. Remark 4J. Menger's Theorem D.1) likewise guarantees that, given any two fc-sets of vertices A":= {xux2,...,xk} and У := {у\,уг,-.-,Ук} in a ^-connected graph G, there are к disjoint paths />,, P2,..., Pk connecting A" and У in G. It does not, however, guarantee that path P, can be so chosen as to connect vertices xt and >,, 1 < i < fc. Such a system is called a k-linkage, and a graph is k-linked if it has a ^-linkage for arbitrary A-sets X and У. The 2-linked graphs were characterized by Seymour A980) and Thomassen A980c). The corresponding concept for edge- disjoint paths is called a weak k-linkage. Thomassen A980c) conjectured that a fc-edge-connected graph is weakly it-linked if к is odd. This would imply that a fc-edge-connected graph is weakly (k - l)-linked if к is even, a result established by Huck A991). Further information on linkages can be found in chapter 2. The Fan Lemma D.2) is a very versatile tool. We give here one illustration of its use, by Dirac A960). Theorem 4.4. Let G be a k-connected graph, where к > 2, and let S be a set of к vertices in G. Then G contains a circuit С that includes every vertex of S. Proof. The theorem is true for к = 2, since the union of two internally-disjoint -ty-paths is a circuit that includes both x and y. We proceed by induction on k. 36 J.A. Bondy Suppose that the theorem holds for к < n, where n > 3. Let G be an я-connected graph, let S be a set of n vertices of G, and let xeS. Put S' :=S\x. Then 5' is a set of л — 1 vertices in the n-connected graph G. By the induction hypothesis, there is a circuit С in G that includes every vertex of S'. If x € V(C'), we may take С := C\ and there is nothing more to prove. Suppose, then, that x g V(C'). Note that the vertices of S' partition С into n -1 segments. There are two cases. If С is of length at least n, we apply the Fan Lemma D.2) with к := n and У := V(C). By the pigeonhole principle, two of the paths whose existence is guaranteed by the lemma, say P, and Ph must terminate at vertices y, and y/ that lie in the same segment of C. The desired circuit С can now be obtained from С by replacing the yty,-segment of С by the у*)",-path />, i> y. If С is of length n -1, we apply the Fan Lemma D.2) with к := n - 1 and У := V(C'), and use the above argument. ? Remark 4S. Watkins and Mcsncr A967) characterized the extremal graphs for Theorem 4.4, that is, those /c-connected graphs in which some set of к + 1 vertices is included in no circuit. For к > 3, they are the ^-connected graphs having a set of к vertices whose deletion leaves a graph with more than к components; there are two additional families of extremal graphs when к = 2. Bermond and Lov?sz A975) conjectured a digraph analogue of Theorem 4.4 for the case к = 2, namely that in a digraph of sufficiently high strong connectivity, any two vertices lie on a common directed circuit. This was disproved by Thomassen A991). Bondy and Lovasz A981) generalized Theorem 4.4 by showing that, if к > 2, the circuits through a set 5 of к vertices in a jt-connected graph G generate the cycle space of G (except in certain specified cases); any circuit of G can, moreover, be expressed as the sum of an odd number of circuits through 5. This implies that there is an even circuit through S and, if G is not bipartite, also an odd circuit through S. Egawa et al. A991) obtained a strong common generalization of Theorem 4.4 and Theorem 2.15. Theorem 4.6. Let G be a simple k-connected graph of minimum degree 8, where к 3: 2, and let S be a set of к vertices ofG. Then G contains either a circuit of length at least 25 that includes every vertex of S or a Hamilton circuit. Establishing the existence of circuits through specified edges is far more chal- challenging. Let ei := xrfi and e2 := *гУ2 be any two edges in a 2-connected graph G. Form a new graph G' by subdividing e, by vh i = 1,2. Then G' is 2-connected and, by Theorem 4.4, there is a circuit in G' that includes both vt and и2- Thus, in G, there is a circuit that includes both «i and e2. This observation cannot be ex- extended to 3-connected graphs; three edges that are incident with the same vertex, or that form an edge cut, do not lie on a common circuit. However, these are the only exceptions, as Adam A963) proved. LovSsz A974) was led to formulate the following general conjecture. Basic graph theory: Paths and circuits 37 Figure 6. Л vine an a path. Conjecture 4.7. Let G be a /c-connected graph, where к > 2, and let S be a set of к edges in G that induce a path system. Then there is a circuit of G that includes every edge of 5, unless к is odd and S is an edge cut of G. A slightly weaker version of this conjecture, due to Woodall A977), was verified by HSggkvist and Thomassen A982). Their proof uses a variant of the Hopping Lemma F.7), to be discussed in section 6. Theorem 4Л. Let G be a k-connected graph, where к > 2, and let S be a set of к — 1 edges in G that induce a path system. Then there is a circuit of G that includes every edge of S. A related conjecture, for 3-reguIar graphs, was formulated by Holton and Thomassen A986). The connectivity hypothesis is replaced here by the less strin- stringent one of cyclic edge connectivity. A connected graph G that contains two disjoint circuits is cyclically k-edge-connected if it has no bond S of fewer than к edges such that both components of G \ S contain circuits. Conjecture 4.9. Let О be a 3-regular cyclically i-edge-connected graph and let S be a set of к -1 edges in G that induce a path system. Then there is a circuit of G that includes every edge of 5. In Theorem 4.4, the Fan Lemma D.2) was used to establish the existence of certain circuits in fc-connected graphs. Another very useful tool in this context, developed by Dirac A952), is that of a vine (see fig. 6). A vine on a path P —P [яг, у] is a set 9 := {Pj[xhy,]: 1 < i < m} of internally-disjoint paths such that (a) P,nP = {xi,yi}, l<i<m; (b) x = x, 4 x2 -< y\ -4 *3 -< Уг -4 *t -< ¦ • -4 *m < Ут-i -< Ут = У on P. Dirac A952) showed that there is a vine on any path in a 2-connected graph. A generalization of this result was given by Bondy and Locke A981). Vines 9, and S>2 on a path P[x,y] are disjoint if (a) the paths of °Р, and 9г are internally-disjoint; (b) the only vertex that is the tail of a path of 9^ and the tail of a path of 9г is *; (c) the only vertex that is the head of a path of 9X and the head of a path of ®2 is y. For sets of vertices X and У in a graph, a path whose tail lies in X and whose head lies in У is called an [X, Y\-path. Lemma 4.10 (The Vine Lemma). Let P be a path in a k-connected graph G. Then there are к — 1 pairwise-disjoint vines ??i, ^: - - -, &к-\ on P. 38 J.A. Bondy Proof. Let P := vqV\ ¦¦¦v(. Since G is Jfc-connected, there are к internally-disjoint uoiv-paths Qx, Qi, ¦ ¦¦, Qk in G. From each path Qt, we construct a family % of paths as follows. If V (P) n V(Q,) := {wx,w2,...,wm}, where wf -< w;+1 on ft, 1 < / $ m — 1, we set We now define 2 := U*=I2,-. It follows from these definitions that if X,:={vo,vu---,Vj-i} and Yj := {uJ+,,u/+2,...,u,}, whereO</<^, then 2, contains an [Л), У^-path avoiding vh for any j such that и, ? V(Q,). Be- Because the paths Qt are internally-disjoint, at most one of them includes any par- particular Vj, and so 9. contains at least к -1 [Xj, y;]-paths avoiding vn for each U o<j<e. We now construct the desired vines inductively. Initially, we select from 2 к — 1 [A^Yi]-paths />,, />2,-¦•, P*-i avoiding ui and set 9>j :={/>,}, 1 < j < Jfc — 1. At each subsequent stage, we modify the families 9>, as follows. Let p, denote the vertex of 9t that is furthest from v0 on P. Upi = p2 = ¦¦= Pk-\ = u^, the families 9j are vines on P satisfying the conditions of the lemma. Otherwise, we define vi '¦= P\< where we assume (relabelling if necessary) that p\ <4p2 =*¦¦• •4pt_i.Bach 9"i, 2 < i < к - 1, contains at most one Щ, Y,]-path avoiding Vj. Therefore, there is at least one more such path Q in 2 \ ufj,19t. Let Uj be the tail of Q. We modify the family <3>x by adding Q and deleting each path whose head lies in P{uhvj\ except the one whose tail is closest to v0; the families &,, 2 sj < < fc - 1, are not modified. This procedure terminates with к — 1 pairwise-disjoint vines 9\ 92 ..., &k-\ °n P- U Dirac A952) used the Vine Lemma D.10) to prove that, if a 2-connected graph has a path of length (, it necessarily has a circuit of length at least 2!}1г. (The grarft of fig. 6 is an extremal graph for this theorem, with / = 25.) The lemma was also applied by Bondy and Locke A981) and Locke A982) to establish analogous results for graphs of higher connectivity; for example, if a 3-connected graph has a path of length /, it necessarily has a circuit of length at least 2^/5. Of particular note here is the marked difference in the behaviour of 2-connected and 3-connected graphs; we shall see further instances of this phenomenon shortly. A similar change may well occur in the passage from 3-connected to 4-connected graphs; several intriguing conjectures support this view, although there is little hard evidence. Dirac A952) also used the Vine Lemma D.10) to prove Theorem 2.15, a gener- generalization of his Theorem 2.1. The same proof technique (see Posa 1963, proof of Theorem 3) yields the corresponding generalization of Ore's Theorem B.4) first stated explicitly by Bermond A976) and Linial A976). Basic graph theory: Paths and circuits 39 Theorem 4.11. Let G be a simple 2-connected graph in which the degree sum of any two nonadjacent vertices is at least d. Then G contains either a circuit of length at least d or a Hamilton circuit. Proof. Let P[x,y] be a longest path in G and 9 := {?,¦[*,-,#]: 1 < i < m) a vine on P; note that P, and Pm are of length one, by the choice of P. Consider the circuit where С; := Р[х"у{\Р" 1 ^ i =Sm, and assume that 9> is chosen so that (i) \9\ = m is as small as possible; (ii) subject to (i), |V(C)n V(P)\ is as large as possible. Set P ~vf,v1v2--vi, where vo :=x, vk := j>i and vt :=y, and define X ¦- {v,: xu,+i € E} and Y := {vr- vLy e E). If X n У ф 0, then (as in Proof 2 of Dirac's Theorem, 2.1) С is a Hamilton circuit of G, since P is a longest path. If X П У = 0, then jt and у are nonadjacent. Moreover, by the choice of 9, С contains every vertex ot(XuYu {у}) \ {vk_t} and thus is of length at least d(x) + d(y). By hypothesis, this is at least d. p One consequence of Theorem 4.11 is a frequently used theorem of Erd6s and Gallai A959). Corollary 4.12. Let G(x,y) be a simple 2-connected graph such that d(v) ^ d, for all ифх,у. Then there is an xy-path of length at least d in G. Proof. Denote by H the graph obtained from G by adding a set S of d - 1 vertices and joining them to one another and to both x and y. Then Я is a simple nonseparable graph on n vertices, where n > 2d > 4, in which the degree sum of any two nonadjacent vertices is at least Id. By Theorem 4.11, H contains a circuit С of length at least Id. If С includes vertices of S, С \ S is an дгу-path in G of length at least d. Otherwise С QG and, because G is 2-connected, there are disjoint paths P\ and P2 in G connecting {x,y} and С In this case, the subgraph CuPi uP2 of G contains two xy-paths, at least one of which is of length at least d. ? Theorem 4.11 is an Ore-type generalization of Theorem 2.15. Voss and Zuluaga A977) generalized the latter theorem in another direction. Theorem 4.13. Let G be a simple nonseparable nonbipartite graph of minimum degree Sonn vertices, where S < n/2 Then G contains both an odd circuit of length at least 25-1 and an even circuit of length at least 28. This clearly implies Theorem 2.15 in the case of nonbipartite graphs. For bipar- bipartite graphs, it suffices to add an edge between two vertices in the same part of the bipartition and then apply Theorem 4.13. We propose the following conjec- conjecture, a strengthening of one mentioned in Locke A985). If true, it would imply Theorem 4.13 in the case of 3-connected graphs. 40 J.A. Bondy Conjecture 4.14. Let G be a simple 3-connected graph of minimum degree S on n vertices, where S < n/2. Then the circuits of length at least 25—1 generate the cycle space of G; moreover, every circuit of