GRAPH THEORY WITH APPLICATIONS

1 GRAPH THEORY . with APPLICATIONS . J. A. Bondy and U. S. R. Murty Department of Combina tories and Optimization, University of Waterloo, Ontario, Canada NORfH-HOLLAND. New York Amsterdam Oxford Bondy and Muny 1976. First published in Great Britain 1976 by The Macmillan Press Ltd. First published in the 1976 by Elsevier Science Publishing Co., Inc. 52 Vanderbilt Avenue, New York, 10017. Fifth Printing, 1982. Sole Distributor in the : Elsevier Science Publishing Co., Inc. Library of Congress Cataloging in Publication Data Bondy, John Adrian. GRAPH THEORY with APPLICATIONS . Bibliography: p. lncludes index. 1. GRAPH THEORY . 1. Murty, , joint author. II. Title. 1979 511 '.5 75-29826. ISBN 0.:444-19451-7. AU rights reserved. No part of this publication may be reproduced or transmitted, in any form or by any means, without permission. Printed in the United States of America To our parents Preface This book is intended as an introduction to GRAPH THEORY .

2 Our aim bas been to present what we consider to be the basic material, together with a wide variety of APPLICATIONS , both to other branches of mathematics and to real-world problems. Included are simple new proofs of theorems of Brooks, Chv tal, Tutte and Vizing. The APPLICATIONS have been carefully selected, and are treated in some depth. We have chosen to omit ail so-called ' APPLICATIONS ' that employ just the language of graphs and no THEORY . The APPLICATIONS appearing at the end of each chapter actually make use of THEORY developed earlier in the same chapter. We have also stressed the importance of efficient methods of solving problems. Several good al- gorithms are included and their efficiencies are analysed. We do not, however, go into the computer iinplementation of these algorithms. The exercises at the end of each section are of varying difficulty. The harder ones are starred (*) and, for these, hints are provided in appendix I.

3 Ln some exercises, new . definitions are introduced. The reader is recom- mended to acquaint himself with these definitions. Other exercises, whose numbers are indicated by bold type, are used in subsequent sections; these should ail be attempted. Appendix II consists of a table in which basic properties of four graphs are listed. When new definitions are introduced, the reader may find it helpful to check bis understanding by referring to this table. Appendix III. includes a selection of interesting graphs with special properties. These may prove to be useful in testing new conjectures. In appendix IV, we collect together a number of unsolved problems, some known to be very difficult, and others more hopeful. Suggestions for further reading are given in appendix V. Many people have contributed, either directly or indirectly, to this book. We are particularly indebted to C. Berge and D. J. ~- Welsh for introducing us to GRAPH THEORY , to G.

4 A. Dirac, J. Edmonds, L. Lov sz and W. T. Tutte, whose works have influenced oui- treatment of the subject, to V. Chungphaisan and C. St. J. A. Nash-Williams for their careful reading of the Preface vii manuscript and valuable suggestions, and to the ubiquitous G. O. M. for his kindness and constant encouragement. We also wish to thank S. B. Maurer, P. J. O'Halloran, C. Thomassen, B. Toft and our colleagues at the University of Waterloo for many helpful comments, and the National Research Council of Canada for its financial support. Finally, we would like to express our appreciation to Joan Selwood for her excellent typing and Diana Rajnovich for her beautiful artwork.. J. A. Bondy U. S. R. Murty Contents Pre/ace vi 1 GRAPHS AND SUBGRAPHS. Graphs and simple Graphs . 1. GRAPH Isomorphism 4. The Incidence and Adjacency Matrices 7. Subgraphs 8. Vertex Degrees 10. Paths and Connection 12. Cycles 14.

5 APPLICATIONS The Shortest Path Problem. 15. Sperner's Lemma. 21. 2 TREES. Trees 25. Cut Edges and Bonds .. 27. Cut Vertices. 31. Cayley's Formula . 32. APPLICATIONS The Connector Problem 36. 3 CONNECTIVITY. Connectivity . 42. Blocks . 44. APPLICATIONS Construction of Reliable Communication Networks 47. 4 EULER TOURS AND HAMILTON CYCLES. Euler Tours . 51. Hamilton Cycles . 53. APPLICATIONS Postman Problem 62. The Travelling Salesman Problem 65. Contents ix 5 MATCHINGS. 5 .1 Matchings 70. 5 .2 Matchings and Coverings in Bipartite Graphs 72. Perfect Matchings . 76. APPLICATIONS The Personnel Assignment Problem 80. The Optimal Assignment Problem 86..6 EDGE COLOURINGS. Edge Chromatic Number 91. Vizing's Theorem . 93. APPLICATIONS 63 The Timetabling Problem 96. 7 INDEPENDENT SETS AND CLIQUES. Independent Sets .. 101. Ramsey's Theorem 103. 7 .3 Turan 's Theorem .. 109. APPLICATIONS Schur's Theorem.

6 112. A Geometry Problem . 113. 8 VERTEX COLOURINGS. Chroniatic Number ..117. Brooks' Theorem .. 122. Haj6s' Conjecture. 123. Chromatic Polynomial~. 125. Girth and Chromatic Number 129. APPLICATIONS A Storage Problem 131. 9 PLANAR GRAPHS. Plane and Planar Graphs 135. Dual Graphs . 139. Euler's Formula .. 143. Bridges .. 145. Kuratowski's Theorem .. 151. The Five-Colour Theorem and the Four-Colour Conjecture 156. Nonhamiltonian Planar Graphs . 160. APPLICATIONS 9 .8 A Planarity Algorithm .. 163. X Contents 10 DIRECTED GRAPHS. Directed Graphs . 171. Directed Paths 173. Directed Cycles 176. APPLICATIONS A Job Sequencing Problem. 179. Designing an Efficient Computer Drum 181. Making a Road System One-Way 182. Ranking the Participants in a Tournament. 185. 11 NETWORKS. Flows 191. Cuts 194. The Max-Flow Min-Cut Theorem 196. APPLICATIONS Menger's Theorems 203. Feasible Flows 206. 12 THE CYCLE SPACE AND BOND SPACE.

7 Circulations and Potential Differences. 212. The Number of Spanning Trees . 218. APPLICATIONS Perfect Squares . 220. Appendix I Hints to Starred Exercises 227. Appendix II Four Graphs and a Table of their Properties . 232. Appendix III Sorne Interesting Graphs. 234. Appendix IV Unsolved Problems. 246. Appendix V Suggestions for Further Reading 254. Glossary of Symbols 257. Index 261. 1 Graphs and Subgraphs GRAPHS AND simple GRAPHS. Many real-world situations can conveniently be described by means of a diagram consisting of a set of points together with lines joining certain pairs of these points. For example, the points could represent people, with lines joining pairs of friends; or the points might be communication centres, with Iines representing communication links. Notice that in such diagrams one is mainly interested in whether or not two given points are joined by a Iine;. the manner in which they are joined is immaterial.

8 A mathematical abstrac- tion of situations of this type gives rise to the concept of a GRAPH . A GRAPH G is an ordered triple (V(G), E(G), t/Jo) consisting of a nonempty set V( G) of vert~ces, a set E( G), disjoint from V( G), of edges, and an incidence function tJ,a that associates with each edge of G an unordered pair of (not necessarily distinct) vertices of G. If e is an edge and u and u are vertices such that t/la(e) = uv, then e is said to join u and v; the vertices u and v are called the ends of e. Two examples of graphs should serve to clarify the definition. Example 1. G = (V(G), E(G), t/lo). where V(G)= {v1, V2, V3, V4, Vs}. E(G) = {e1, e2, e3, e4, es, e6, e,, es}. and tj,c; is defined by t/la(e1) = V1 V2, t/lo(e2) = V2V3, tpa(e3) = V3V3, t/la(e4) = V3V4. t/la(es) = V2V4, t/la(e6) = V4Vs, t/la(e,) = V2Vs, t/lo(es) = V2Vs Example 2. H = (V(H), E(H), t/lH). where V(H) = {u, v, w, x, y}.

9 E(H) = {a, b, c, d, e, f, g, h}. and 'PH is defined by tpH( Q) = UV, t/lH(b) = uu, t/lH(c) = vw, t/lH(d) = wx t/JH( e) = VX, t/lH(/) = WX, t/JH(g) = UX, t/lH(h) = xy 2 GRAPH THEORY with APPLICATIONS b w G H. Figure Diagrams of graphs G and H. Graphs are so named because they can be represented graphically, and it is this graphical representation which helps us understand many of their properties. Each vertex is indicated by a point, and each edge by a line joining the points which represent its ends. t Diagrams of G and H are shown in figure 1. 1. (For clarity, vertices are depicted here as small circles.). There is no unique way of drawing a GRAPH ; the relative positions of points representing vertices and lines representing edges have no significance. Another diagram of G, for example, is given in figure A diagram of a GRAPH merely depicts the incidence relation holding between its vertices and edges.

10 We shall, however, often draw a diagram of a GRAPH and refer toit as the GRAPH itself; in the same spirit, we shall call its points 'vertices' and its lines 'edges'. Note that two edges in a diagram of a GRAPH may intersect at a point that Figure Another diagram of G. t. In such a drawing it is understood that no line intersects itself or passes through a point representing a vertex which is not an end of the corresponding edge-this is clearly always possible. Graphs and Subgraphs 3. is not a vertex (for .example e1 and e6 of GRAPH G in figure ). Those graphs that have a diagram whose edges intersect only at their ends are called plarlar, since such graphs can be represented in the plane in a simple manner. The GRAPH of figure is planar, even though this is not immediately clear from the particular representation shown (see exercise ). The GRAPH of figure , on the other band, is nonplanar. (This will be proved in chapter 9.)