text:
More Topics
Creator's Hub
Collect Leads
Get Started
Tips & Tricks
For Business
Introduction to graph theory
Upcoming SlideShare
Loading in...
Like this document? Why not share!
Connectivity of graph
by Shameer P Hamsa
6132 views
Computer Science Engineering: Discr...
by klirantga
1520 views
Graph theory narsingh deo
by Umang Gupta
7729 views
Music theory for dummies
by Edgar Arruda
926 views
Mitigation of harmonics using thyri...
by eSAT Publishing H...
144 views
Ap u.s. history for dummies free pd...
by 帅 林
2306 views
Share SlideShare
Email sent successfully!
Size (px)
Start on
Show related SlideShares at end
WordPress Shortcode
Introduction to graph theory
Gonzalo Santiago
, CEO & Founder
Didxaza traducciones & Simplesoft Mx.
Published on
Dec 06, 2013
Published in:
2 Comments
Full Name
Comment goes here.
12 hours ago
Are you sure you want to
Your message goes here
Krishnan Paramasivam
Assistant Professor at National Institute of Technology Calicut
National Intitute of Technology Calicut
good one...thanks
1 month ago
Are you sure you want to
Your message goes here
Gonzalo Santiago
CEO & Founder
Didxaza traducciones & Simplesoft Mx.
friendme on Facebook because i dont remember my email password
1 year ago
Are you sure you want to
Your message goes here
State University of Medan
State University of Medan
2 months ago
Nilaksha Rathnayake
UI Engineer
9 months ago
10 months ago
1 year ago
1 year ago
No Downloads
Total Views
On Slideshare
From Embeds
Number of Embeds
No embeds
No notes for slide
Transcript of "Introduction to graph theory"
1. Introduction to Graph Theory 5th Edition G. Jones, University of Southampton 'If this book did not exist, it would be necessary to invent it!' B. Cooper, University of Leeds 'I have always regarded Wilson's book as THE undergraduate textbook on graph theory, without a rival' D. Sharpe, University of Sheffield 5th Edition Introduction to Graph Theory Robin J. Wilson Robin J. Wilson Robin Wilson is Emeritus Professor of Pure Mathematics at the Open University, and Emeritus Professor of Geometry at Gresham College, London. He is also a former Fellow in Mathematics at Keble College, Oxford University, and now teaches at Pembroke College. He has written and edited almost 40 books on graph theory, combinatorics, the history of mathematics, and music, and is very involved with the communication and popularisation of mathematics. 5th Edition In recent years graph theory has emerged as a subject in its own right, as well as being an important mathematical tool in such diverse subjects as operational research, chemistry, sociology and genetics. Robin Wilson's book has been widely used as a text for undergraduate courses in mathematics, computer science and economics, and as a readable introduction to the subject for non-mathematicians. The opening chapters provide a basic foundation course, containing definitions and examples, connectedness, Eulerian and Hamiltonian paths and cycles, and trees, with a range of applications. This is followed by two chapters on planar graphs and colouring, with special reference to the four-colour theorem. The next chapter deals with transversal theory and connectivity, with applications to network flows. A final chapter on matroid theory ties together material from earlier chapters, and an appendix discusses algorithms and their efficiency. For this new edition the text has been revised throughout, and several sections have been reorganised and renumbered. Some new material has been added – notably on the proof of the four-colour theorem, the bracing of rectangular frameworks and algorithms – the number of exercises has been increased and more solutions are provided. Introduction to Graph Theory 'An excellent introduction on an increasingly popular topic' www.pearson-books.com CVR_WILS8894_05_SE_CVR.indd 1 26/4/10 15:53:31
A01_LOWE7798_01_SE_FM.indd 10 05/03/2010 09:51
Introduction to Graph Theory
We work with leading authors to develop the strongest educational materials in mathematics, bringing cutting-edge thinking and best learning practice to a global market. Under a range of well-known imprints, including Prentice Hall, we craft high quality print and electronic publications which help readers to understand and apply their content, whether studying or at work. To find out more about the complete range of our publishing, please visit us on the World Wide Web at: www.pearsoned.co.uk
Introduction to Graph Theory Fifth Edition Robin J. Wilson
Pearson Education Limited Edinburgh Gate Harlow Essex CM20 2JE England and Associated Companies throughout the world Visit us on the World Wide Web at: www.pearsoned.co.uk First published by Oliver & Boyd 1972 Second edition published by Longman Group Ltd 1979 Third edition 1985 Fourth edition 1996 Fifth edition published 2010 © Robin Wilson 1972, 2010 The right of Robin Wilson to be identified as author of this work has been asserted by him in accordance with the Copyright, Designs and Patents Act 1988. All rights reserved. No part 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 either the prior written permission of the publisher or a licence permitting restricted copying in the United Kingdom issued by the Copyright Licensing Agency Ltd, Saffron House, 6–10 Kirby Street, London EC1N 8TS. ISBN: 978-0-273-72889-4 British Library Cataloguing-in-Publication Data A catalogue record for this book is available from the British Library Library of Congress Cataloging-in-Publication Data Wilson, Robin J. Introduction to graph theory / Robin J. Wilson. – 5th ed. p. cm. Includes bibliographical references and index. ISBN 978-0-273-72889-4 (pbk.) 1. Graph theory. I. Title. QA166.W55 2010 511′.5–dc22 2010009905 10 9 8 7 6 5 4 3 2 1 14 13 12 11 10 Typeset in 10/12pt Times by 35 Printed and bound by Ashford Colour Press Ltd., Gosport, Hampshire.
Contents Preface to the fifth edition vii Introduction 1 1 Definitions and examples 8 1.1 1.2 1.3 1.4 2 Definitions Examples Variations on a theme Three puzzles 8 18 22 26 32 2.1 2.2 2.3 2.4 3 Paths and cycles 32 40 47 52 Connectivity Eulerian graphs and digraphs Hamiltonian graphs and digraphs Applications 61 3.1 3.2 3.3 4 Trees 61 65 70 Properties of trees Counting trees More applications 80 4.1 4.2 4.3 4.4 5 Planarity 80 86 91 96 Planar graphs Euler's formula Dual graphs Graphs on other surfaces Colouring graphs 101 5.1 5.2 5.3 5.4 5.5 101 107 111 117 122 Colouring vertices Chromatic polynomials Colouring maps The four-colour theorem Colouring edges
vi Contents 6 128 6.1 6.2 6.3 7 Matching, marriage and Menger's theorem 128 134 138 Hall's 'marriage' theorem Menger's theorem Network flows Matroids 145 7.1 7.2 7.3 145 149 152 Introduction to matroids Examples of matroids Matroids and graphs Appendix 1: Algorithms Appendix 2: Table of numbers List of symbols Bibliography Solutions to selected exercises Index Go forth, my little book! pursue thy way! Go forth, and please the gentle and the good. William Wordsworth 158 161 162 163 166 181
Preface In recent years, graph theory has established itself as an important mathematical tool in a wide variety of subjects, ranging from operational research and chemistry to genetics and linguistics, and from computer science and geography to sociology and architecture. At the same time it has also emerged as a worthwhile mathematical discipline in its own right. In view of this, there has been a need for an inexpensive introductory text on the subject, suitable both for mathematicians taking courses in graph theory and for non-specialists wishing to learn the subject as quickly as possible. It is my hope that this latest edition continues to go some way towards filling this need. The only prerequisites to reading it are a basic knowledge of elementary set theory and matrix theory, although a further knowledge of abstract algebra and topology is needed for a few of the more difficult exercises. The contents of this book may be conveniently divided into four parts. The first of these (Chapters 1–3) provides a basic foundation course, containing definitions and examples of graphs and digraphs, connectedness, Eulerian and Hamiltonian paths and cycles, and trees. This is followed by two chapters (Chapters 4 and 5) on planarity and colouring, with special reference to the four-colour theorem. The third part (Chapter 6) deals with transversal theory and connectivity, with applications to network flows. The book ends with a chapter on matroids (Chapter 7), which ties together material from the previous chapters and introduces some recent developments. Throughout the book I have attempted to restrict the text to basic material. Of the 300 exercises, many are routine examples designed to test understanding of the text, while others will introduce you to new results and ideas. You should read each exercise, whether or not you work through it in detail, as some are referred to later in the book. Solutions are given for some of the exercises; these exercises are indicated by the symbol s next to the exercise number. More difficult exercises (called Challenge problems) appear at the end of each chapter. I have used the symbol ■ to indicate the end of a proof, and bold-face type is used for definitions. The number of elements in a set S is denoted by | S |, and the empty set is denoted by Ø. A substantial number of changes have been made in this edition. The text has been revised throughout and several sections have been rearranged and renumbered. Some new material has been added – notably on the four-colour theorem and on algorithms – and other material has been removed. Several further changes have arisen as a result of comments by a number of people, and I should like to thank them for their helpful remarks.
viii Preface to the fifth edition Finally, I wish to express my thanks to my former students, but for whom this book would have been completed earlier, to Mr William Shakespeare and others for their apt and witty comments at the beginning of each chapter, and most of all to my wife Joy for many things that have nothing to do with graph theory. R.J.W. November 2009
Introduction The last thing one discovers in writing a book is what to put first. Blaise Pascal In this Introduction we provide an intuitive background to the material that we present more formally later on. Terms that appear here in bold-face type are to be thought of as descriptions rather than as definitions; having met them here in an informal setting, you should find them more familiar when you meet them later. So read this Introduction quickly, and then forget all about it! What is a graph? We begin by considering Figs 0.1 and 0.2, which depict part of a road map and part of an electrical network. Figure 0.1 Figure 0.2 Either of these situations can be represented diagrammatically by means of points and lines, as in Fig. 0.3. The points P, Q, R, S and T are called vertices, the lines are called edges, and the whole diagram is called a graph. Note that the intersection of the lines PS and QT is not a vertex, since it does not correspond to a crossroads or to the meeting of two wires. The degree of a vertex is the number of edges with that vertex as an end-point; it corresponds in Fig. 0.1 to the number of roads at an intersection. For example, the degree of the vertex P is 3 and the degree of the vertex Q is 4. Figure 0.3
2 Introduction The graph in Fig. 0.3 can also represent other situations. For example, if P, Q, R, S and T represent football teams, then the existence of an edge might correspond to the playing of a game between the teams at its end-points. Thus, in Fig. 0.3, team P has played against teams Q, S and T, but not against team R. In this representation, the degree of a vertex is the number of games played by that team. Another way of depicting these situations is to use the graph in Fig. 0.4. Here we have removed the 'crossing' of the lines PS and QT by redrawing the line PS outside the rectangle PQST. The resulting graph still tells us whether there is a direct road from one intersection to another, how the electrical network is wired up, and which football teams have played which. The only information we have lost concerns 'metrical' properties, such as the length of a road and the straightness of a wire. Thus, a graph is a representation of a set of points and of how they are joined up, and any metrical properties are irrelevant. From this point of view, any graphs that represent the same situation, such as those of Figs 0.3 and 0.4, are regarded as the same graph. Figure 0.4 More generally, two graphs are the same if two vertices are joined by an edge in one graph if and only if the corresponding vertices are joined by an edge in the other. Another graph that is the same as those in Figs 0.3 and 0.4 is shown in Fig. 0.5. Here all idea of space and distance has gone, but we can still tell at a glance which points are joined by a road or a wire. Figure 0.5 In this graph there is at most one edge joining each pair of vertices. Suppose now that in Fig. 0.5 the roads joining Q and S, and S and T, have too much traffic to carry. Then we can ease the situation by building extra roads joining these points, and the resulting diagram looks like Fig. 0.6. The edges joining Q and S, or S and T, are called multiple edges. If, in addition, we need a car park at P, then we indicate this by drawing an edge from P to itself, called a loop (see Fig. 0.7). In this book, graphs may
Introduction 3 Figure 0.6 Figure 0.7 contain loops and multiple edges; graphs with no loops or multiple edges, such as the graph in Fig. 0.5, are called simple graphs. The study of directed graphs (or digraphs, as we abbreviate them) arises from making the roads into one-way streets. An example of a digraph is given in Fig. 0.8, with the directions of the one-way streets indicated by arrows; such a 'directed edge' is called an arc. (In this example, there would be chaos at T, but that does not stop us from studying such situations!) Figure 0.8 Much of graph theory is devoted to 'walks' of various kinds. A walk is a 'way of getting from one vertex to another' in a graph or digraph, and consists of a sequence of edges or arcs, one following after another. For example, in Fig. 0.5, P 2 Q 2 R is a walk of length 2, and P 2 S 2 Q 2 T 2 S 2 R is a walk of length 5. A walk in which no vertex appears more than once is called a path; for example, P 2 T 2 S 2 R is a path. A walk of the form Q 2 S 2 T 2 Q, in which no vertex appears more than once, except for the beginning and end vertices which coincide, is called a cycle. In Chapter 2 we also consider walks with some extra property. In particular, we discuss graphs and digraphs containing walks that include every edge exactly once and end back at the initial vertex; such graphs and digraphs are called Eulerian. The graph in Fig. 0.5 is not Eulerian, since any walk that includes each edge exactly once (such as P 2 Q 2 R 2 S 2 T 2 P 2 S 2 Q 2 T ) must end at a vertex different from the initial one. We also discuss graphs and digraphs containing cycles that pass through every vertex; these are called Hamiltonian. For example, the graph in Fig. 0.5 is Hamiltonian; a suitable cycle is P 2 Q 2 R 2 S 2 T 2 P. Some graphs or digraphs are in two or more parts. For example, consider the graph whose vertices are the stations of the London Underground and the New York Subway,
4 Introduction and whose edges are the lines joining adjacent stations. It is clearly impossible to travel from Trafalgar Square to Grand Central Station using only edges of this graph, but if we confine our attention to the London Underground part only, then we can travel from any station to any other. A graph or digraph that is 'in one piece', so that any two vertices are connected by a path, is connected; a graph or digraph that is in more than one piece is disconnected (see Fig. 0.9). We discuss connectedness in Chapters 1, 2 and 6. We are sometimes interested in connected graphs with only one path between each pair of vertices. These graphs contain no cycles and are called trees (see Fig. 0.10). They generalize the idea of a family tree, and are considered in Chapter 3. Figure 0.9 Figure 0.10 Earlier we saw how the graph of Fig. 0.3 can be redrawn as in Figs 0.4 and 0.5 so as to avoid crossings of edges. Any graph that can be redrawn without crossings in this way is called a planar graph. In Chapter 4 we give several criteria for planarity. Some of these involve the properties of particular 'subgraphs' of the graph in question; others involve the fundamental notion of duality. Planar graphs also play an important role in colouring problems. In our 'road-map' graph, let us suppose that Shell, Esso, BP and Gulf wish to erect five garages between them, and that for economic reasons no company wishes to erect two garages at neighbouring corners. Then Shell can build at P, Esso can build at Q, BP can build at S, and Gulf can build at T, leaving either Shell or Gulf to build at R (see Fig. 0.11). However, if Gulf backs out of the agreement, then the other three companies cannot erect their garages in the specified manner. Figure 0.11
Introduction 5 We discuss such problems in Chapter 5, where we try to colour the vertices of a simple graph with a given number of colours so that each edge of the graph joins vertices of different colours. If the graph is planar, then we can always colour its vertices in this way with only four colours – this is the celebrated four-colour theorem. Another version of this theorem is that we can always colour the countries of any map with four colours so that no two neighbouring countries share the same colour (see Fig. 0.12). Figure 0.12 In Chapter 6 we investigate the celebrated marriage problem, which asks under what conditions a collection of girls, each of whom knows several boys, can be married so that each girl marries a boy she knows. This problem can be expressed in the language of a branch of set theory called 'transversal theory', and is related to problems of finding disjoint paths connecting two given vertices in a graph or digraph. Chapter 6 concludes with a discussion of network flows and transportation problems. Suppose that we have a transportation network such as in Fig. 0.13, in which P is a factory, R is a market, and the edges of the graph are channels through which goods can be sent. Each channel has a capacity, indicated by a number next to the edge, representing the maximum amount of a commodity that can pass through that channel. The problem is to determine how much of the commodity can be sent from the factory to the market without exceeding the capacity of any channel. Figure 0.13 We conclude with a chapter on matroids. This ties together the material of the previous chapters, and follows the maxim 'be wise – generalize!' Matroid theory, the study of sets with 'independence structures' defined on them, generalizes both the linear independence of vectors and some results on graphs and transversals from earlier in the book. However, matroid theory is far from being 'generalization for
6 Introduction generalization's sake'. On the contrary, it gives us clearer insights into several graphical results involving cycles and planar graphs, and provides simple proofs of results on transversals that are awkward to prove by more traditional methods. Matroids have played an important role in the development of combinatorial ideas in recent years. We hope that this Introduction has been useful in setting the scene and describing some of the treats that lie ahead. We now embark upon a formal treatment of the subject. Exercises 0.1s Write down the number of vertices, the number of edges and the degree of each vertex in: (i) the graph in Fig. 0.3; (ii) the tree in Fig. 0.14. Figure 0.14 Figure 0.15 0.2 Draw the graph representing the road system in Fig. 0.15, and write down the number of vertices, the number of edges and the degree of each vertex. 0.3s Figure 0.16 represents the chemical molecules of methane (CH4) and propane (C3H8). (i) Regarding these diagrams as trees, what can you say about the vertices representing carbon atoms (C) and hydrogen atoms ( H)? (ii) Draw a tree that represents the molecule with formula C2H6 (hexane). (iii) There are two different chemical molecules with formula C4H10. Draw trees that represent these molecules. Figure 0.16 0.4 Draw a graph that represents the family tree in Fig. 0.17. Figure 0.17
Introduction 7 0.5s John likes Joan, Jean and Jane; Joe likes Jane and Joan; Jean and Joan like each other. Draw a digraph illustrating these relationships between John, Joan, Jean, Jane and Joe. 0.6 Snakes eat frogs and birds eat spiders; birds and spiders both eat insects; frogs eat snails, spiders and insects. Draw a digraph representing this predatory behaviour. 0.7 Draw a graph with vertices A, B, . . . , M that shows the various routes that one can take when tracing the Hampton Court maze in Fig. 0.18. Figure 0.18
Chapter 1 Definitions and examples I hate definitions! Benjamin Disraeli In this chapter, we lay the foundations for a proper study of graph theory. Section 1.1 formalizes some of the graph ideas in the Introduction, Section 1.2 provides a variety of examples, and Section 1.3 presents two variations on the basic idea. In Section 1.4 we show how graphs can be used to represent and solve three problems from recreational mathematics. More substantial applications are deferred until Chapters 2 and 3, when we have more machinery at our disposal. 1.1 Definitions A simple graph G consists of a non-empty finite set V(G) of elements called vertices (or nodes or points) and a finite set E(G) of distinct unordered pairs of distinct elements of V(G) called edges (or lines). We call V(G ) the vertex-set and E(G) the edge-set of G. An edge {v, w} is said to join the vertices v and w, and is usually abbreviated to vw. For example, Fig. 1.1 represents the simple graph G whose vertex-set V(G) is {u, v, w, z}, and whose edge-set E(G) consists of the edges uv, uw, vw and wz. In any simple graph there is at most one edge joining a given pair of vertices. However, many results for simple graphs also hold for more general objects in which two vertices may have several edges joining them; such edges are called multiple edges. In addition, we may remove the restriction that an edge must join two distinct vertices, and allow loops – edges joining a vertex to itself. The resulting object, with loops and multiple edges allowed, is called a general graph – or, simply, a graph (see Fig. 1.2). Note that every simple graph is a graph, but not every graph is a simple graph. Figure 1.1 Figure 1.2
1.1 Definitions 9 Thus, a graph G consists of a non-empty finite set V(G) of elements called vertices and a finite family E(G) of unordered pairs of (not necessarily distinct) elements of V(G) called edges; the use of the word 'family' permits the existence of multiple edges. We call V(G) the vertex-set and E(G) the edge-family of G. An edge {v, w} is said to join the vertices v and w, and is again abbreviated to vw. Thus in Fig. 1.2, V(G) is the set {u, v, w, z} and E(G) consists of the edges uv, vv (twice), vw (three times), uw (twice) and wz. Note that each loop vv joins the vertex v to itself. Although we sometimes need to restrict our attention to simple graphs, we shall prove our results for general graphs whenever possible. Remark. The language of graph theory is not standard – all authors have their own terminology. Some use the term 'graph' for what we call a simple graph, while others use it for graphs with directed edges, or for graphs with infinitely many vertices or edges; we discuss these variations in Section 1.3. Any such definition is perfectly valid, provided that it is used consistently. In this book: All graphs are finite and undirected, with loops and multiple edges allowed unless specifically excluded. Isomorphism Two graphs G1 and G2 are isomorphic if there is a one–one correspondence between the vertices of G1 and those of G2 such that the number of edges joining any two vertices of G1 equals the number of edges joining the corresponding vertices of G2. For example, the two graphs in Fig. 1.3 are isomorphic, under the correspondence u 3 l, v 3 m, w 3 n, x 3 p, y 3 q, z 3 r. Figure 1.3 For many problems, the labels on the vertices are unnecessary and we drop them. We then say that two 'unlabelled graphs' are isomorphic if we can assign labels to their vertices so that the resulting 'labelled graphs' are isomorphic. For example, we regard the unlabelled graphs in Fig. 1.4 as isomorphic, since the labelled graphs in Fig. 1.3 are isomorphic. The difference between labelled and unlabelled graphs becomes more apparent when we try to count them. For example, if we restrict ourselves to graphs with three vertices, then there are eight different labelled graphs (see Fig. 1.5), but only four
10 Definitions and examples Figure 1.4 Figure 1.5 Figure 1.6 unlabelled ones (see Fig. 1.6). It is usually clear from the context whether we are referring to labelled or unlabelled graphs. Connected graphs We can combine two graphs to make a larger graph. If the two graphs are G1 and G2 and their vertex-sets V(G1) and V(G2) are disjoint, then their union G1 ʜ G2 is the graph with vertex-set V(G1) ʜ V(G2) and edge-family E(G1) ʜ E(G2) (see Fig. 1.7). Most of the graphs discussed so far have been 'in one piece'. A graph is connected if it cannot be expressed as a union of graphs, and disconnected otherwise. Clearly, any disconnected graph G can be expressed as the union of connected graphs, each of which is called a component of G; a disconnected graph with three components is shown in Fig. 1.8. Figure 1.7
1.1 Definitions 11 Figure 1.8 When proving results about graphs in general, we can often obtain the corresponding results for connected graphs and then apply them to each component separately. A table of all the unlabelled connected simple graphs with up to five vertices is given in Fig. 1.9. Figure 1.9
12 Definitions and examples Adjacency and degrees We say that two vertices v and w of a graph are adjacent if there is an edge vw joining them, and the vertices v and w are then incident with such an edge. We also say that two distinct edges e and f are adjacent if they have a vertex in common (see Fig. 1.10). Figure 1.10 The degree of a vertex v is the number of edges incident with v, and is written deg(v); when calculating the degree of v, we usually make the convention that a loop at v contributes 2 (rather than 1) to deg(v). A vertex of degree 0 is an isolated vertex and a vertex of degree 1 is an end-vertex. Thus each of the two graphs in Fig. 1.11 has two end-vertices and three vertices of degree 2, while the graph in Fig. 1.12 has one end-vertex, one vertex of degree 3, one of degree 6 and one of degree 8. The degree sequence of a graph consists of the degrees written in increasing order, with repeats where necessary. For example, the degree sequences of the graphs in Figs 1.11 and 1.12 are (1, 1, 2, 2, 2) and (1, 3, 6, 8). Figure 1.11 Figure 1.12 The earliest result on graph theory is essentially due to Leonhard Euler in 1735 (although he did not express it in the language of graphs). It is sometimes called the handshaking lemma. THEOREM 1.1 (Handshaking lemma) In any graph the sum of all the vertexdegrees is an even number. Proof. The sum of all the vertex-degrees is equal to twice the number of edges, since each edge contributes exactly 2 to the sum. It is thus an even number. ■ The handshaking lemma is so called because it tells us that if several people shake hands, then the total number of hands shaken must be even – this is precisely because just two hands are involved in each handshake. A useful corollary of the handshaking lemma is the following: COROLLARY 1.2 In any graph the number of vertices of odd degree is even.
1.1 Definitions 13 Proof. If the number of vertices of odd degree were odd, then the sum of the vertexdegrees would also be odd, contradicting Theorem 1.1. So the number is even. ■ Subgraphs A graph H is a subgraph of a graph G if each of its vertices belongs to V(G) and each of its edges belongs to E(G). Thus the graph in Fig. 1.13 is a subgraph of the graph in Fig. 1.14, but is not a subgraph of the graph in Fig. 1.15, since the latter graph contains no 'triangles'. Figure 1.13 Figure 1.14 Figure 1.15 We can obtain subgraphs of a graph by deleting edges and vertices. If e is an edge of a graph G, we denote by G - e the graph obtained from G by deleting the edge e; more generally, if F is any set of edges in G, we denote by G - F the graph obtained by deleting the edges in F. Similarly, if v is a vertex of G, we denote by G - v the graph obtained from G by deleting the vertex v together with the edges incident with v; more generally, if S is any set of vertices in G, we denote by G - S the graph obtained by deleting the vertices in S and all edges incident with any of them. An example is shown in Fig. 1.16. Figure 1.16 We also denote by G e the graph obtained by taking an edge e and 'contracting' it – that is, removing it and identifying its ends v and w so that the resulting vertex is incident with all those edges (other than e) that were originally incident with v or w. An example is shown in Fig. 1.17.
14 Definitions and examples Figure 1.17 The complement of a simple graph If G is a simple graph with vertex-set V(G), its complement ı is the simple graph with vertex-set V(G) in which two vertices are adjacent if and only if they are not adjacent in G; Fig. 1.18 shows a graph and its complement. Note that the complement of ı is G. Figure 1.18 Matrix representations Although it is convenient to represent a graph by a diagram of points joined by lines, such a representation may be unsuitable if we wish to store a large graph in a computer. One way of storing a simple graph is by listing the vertices adjacent to each vertex of the graph. An example of this is given in Fig. 1.19. Figure 1.19 Other useful representations involve matrices. If G is a graph without loops, with vertices labelled {1, 2, . . . , n}, its adjacency matrix A is the n ¥ n matrix whose ijth entry is the number of edges joining vertex i and vertex j. If, in addition, the edges are labelled {1, 2, . . . , m}, its incidence matrix M is the n ¥ m matrix whose ijth entry is 1 if vertex i is incident to edge j, and is 0 otherwise. Figure 1.20 shows a labelled graph G with its adjacency and incidence matrices.
1.1 Definitions 15 Figure 1.20 Exercises 1.1s Write down the vertex-set and edge-set of each graph in Fig. 1.3. 1.2 Write down the vertex-set and edge-family of the graph in Fig. 1.21. Figure 1.21 1.3 Draw (i) a simple graph, (ii) a non-simple graph with no loops, (iii) a non-simple graph with no multiple edges, each with five vertices and eight edges. 1.4s By suitably labelling the vertices, show that the two graphs in Fig. 1.22 are isomorphic. Figure 1.22 1.5s Explain why the two graphs in Fig. 1.23 are not isomorphic. Figure 1.23
16 Definitions and examples 1.6 Are the graphs in Fig. 1.24 isomorphic? Figure 1.24 1.7 Classify the following statements as true or false: (i) any two isomorphic graphs have the same degree sequence; (ii) any two graphs with the same degree sequence are isomorphic. 1.8s Locate each of the graphs in Fig. 1.25 in the table of Fig. 1.9. Figure 1.25 1.9 Locate each of the graphs in Fig. 1.26 in the table of Fig. 1.9. Figure 1.26 1.10 (i) Show that there are exactly 2n(n-1)/2 labelled simple graphs on n vertices. (ii) How many of these have exactly m edges? 1.11s Write down the degree sequence of each graph with four vertices in Fig. 1.9, and verify that the handshaking lemma holds for each graph. 1.12 Write down the degree sequence of each graph with five vertices in Fig. 1.9, and verify that the handshaking lemma holds for each graph. 1.13 (i) Draw a graph on six vertices with degree sequence (3, 3, 5, 5, 5, 5); does there exist a simple graph with these degrees? (ii) How are your answers to part (i) changed if the degree sequence is (2, 3, 3, 4, 5, 5)?
1.1 Definitions 17 1.14 (i) Let G be a graph with four vertices and degree sequence (1, 2, 3, 4). Write down the number of edges of G, and construct such a graph. (ii) Are there any simple graphs with four vertices and degree sequence (1, 2, 3, 4)? 1.15 If G is a simple graph with at least two vertices, prove that G must contain two or more vertices of the same degree. 1.16s Which graphs in Fig. 1.27 are subgraphs of the graphs in Fig. 1.22? Figure 1.27 1.17 Let G be the graph of Fig. 1.3 and let e be the edge ux. Draw the graphs G - e and G e. 1.18 Let G be a graph with n vertices and m edges, and let v be a vertex of G of degree k and e be an edge of G. How many vertices and edges have G - e, G - v and G e? 1.19 Draw the complements of the graphs in Figs. 1.13, 1.14 and 1.15. 1.20s Write down the adjacency and incidence matrices of the graph in Fig. 1.28. Figure 1.28 1.21 Write down the adjacency and incidence matrices of the graph in Fig. 1.2. 1.22 Draw the graph whose adjacency matrix is given in Fig. 1.29. Figure 1.29
18 Definitions and examples 1.23 Draw the graph whose incidence matrix is given in Fig. 1.30. Figure 1.30 1.24 If G is a graph without loops, what can you say about the sum of the entries in (i) any row or column of the adjacency matrix of G? (ii) any row of the incidence matrix of G? (iii) any column of the incidence matrix of G? 1.2 Examples In this section we examine some important types of graphs. You should become familiar with them, as they will appear frequently in examples and exercises. Null graphs A graph whose edge-set is empty is a null graph; note that each vertex of a null graph is isolated. We denote the null graph on n vertices by Nn: the graph N4 is shown in Fig. 1.31. Null graphs are not very interesting. Figure 1.31 Complete graphs A simple graph in which each pair of distinct vertices are adjacent is a complete graph. We denote the complete graph on n vertices by Kn: the graphs K4 and K5 are shown in Fig. 1.32. You should check that Kn has 1/2 n(n - 1) edges. Figure 1.32
1.2 Examples 19 Cycle graphs, path graphs and wheels A connected graph in which each vertex has degree 2 is a cycle graph. We denote the cycle graph on n vertices by Cn. The graph obtained from Cn by removing an edge is the path graph on n vertices, denoted by Pn. The graph obtained from Cn-1 by joining each vertex to a new vertex v is the wheel on n vertices, denoted by Wn. The graphs C6, P6 and W6 are shown in Fig. 1.33. Figure 1.33 Regular graphs A graph in which each vertex has the same degree is a regular graph. If each vertex has degree r, the graph is regular of degree r or r-regular. Note that the null graph Nn is regular of degree 0, the cycle graph Cn is regular of degree 2, and the complete graph Kn is regular of degree n - 1. Of special importance are the cubic graphs, which are regular of degree 3; an example of a cubic graph is the Petersen graph, shown in Fig. 1.34. Figure 1.34 Platonic graphs Of interest among the regular graphs are the Platonic graphs, formed from the vertices and edges of the five regular (Platonic) solids – the tetrahedron, octahedron, cube, icosahedron and dodecahedron (see Fig. 1.35).
20 Definitions and examples Figure 1.35 Bipartite graphs If the vertex-set of a graph G can be split into two disjoint sets A and B so that each edge of G joins a vertex of A and a vertex of B, then G is a bipartite graph (see Fig. 1.36). Alternatively, a bipartite graph is one whose vertices can be coloured black and white in such a way that each edge joins a black vertex (in A) and a white vertex (in B). We sometimes write G = G(A, B) when we wish to specify the sets A and B. Figure 1.36 A complete bipartite graph is a bipartite graph in which each vertex in A is joined to each vertex in B by just one edge. We denote the complete bipartite graph with r black vertices and s white vertices by Kr, s: the graphs K1,3, K2,3, K3,3 and K4,3 are shown in Fig. 1.37. You should check that Kr, s has r + s vertices and rs edges. Figure 1.37
1.2 Examples 21 Cubes Of interest among the regular bipartite graphs are the cubes. The k-cube Qk is the graph whose vertices correspond to the sequences (a1, a2, . . . , ak), where each ai = 0 or 1, and whose edges join those sequences that differ in just one place. The graph Q3 (the graph of the cube) is shown in Fig. 1.38 and Q4 appears on the cover. Note that Qk has 2k vertices and is regular of degree k. Figure 1.38 Exercises 1.25s Draw the following graphs: (i) the null graph N5; (ii) the complete graph K 6; (iii) the complete bipartite graph K2,4; (iv) the union of K1,3 and W4 ; (v) the complement of the cycle graph C4. 1.26s In the table of Fig. 1.9, locate all the regular graphs and the bipartite graphs. 1.27s How many edges has each of the following graphs: (i) K10; (ii) K5,7; (iii) Q 4; (iv) W8; (v) the Petersen graph? 1.28 How many edges has each of the following graphs: (i) K12; (ii) K 6,8; (iii) Q5; (iv) W10; (v) the complement of C8? 1.29 If G has n vertices and is regular of degree r, how many edges has G? Use your answer to check the number of edges in the Petersen graph and the k-cube Qk. 1.30 How many vertices and edges has each of the Platonic graphs? 1.31 Give an example (if it exists) of each of the following: (i) a bipartite graph that is regular of degree 5; (ii) a bipartite Platonic graph; (iii) a complete graph that is a wheel; (iv) a cubic graph with 11 vertices; (v) a graph (other than K5, K 4,4 or Q 4) that is regular of degree 4. 1.32s Draw all the simple cubic graphs with at most eight vertices. 1.33 What can you say about the complement of a complete graph, and the complement of a complete bipartite graph?
22 Definitions and examples 1.34 The complete tripartite graph Kr,s,t consists of three sets of vertices (of sizes r, s and t), with an edge joining two vertices if and only if they lie in different sets. Draw the graphs K2,2,2 and K3,3,2 and find the number of edges of K3,4,5. 1.3 Variations on a theme In this section we consider two variations on the definition of a graph. In the first of these, each edge is given a particular direction, as in a one-way street. In the second, we allow our vertex-set and/or edge-set to be infinite. Digraphs A directed graph, or digraph, D consists of a non-empty finite set V(D) of elements called vertices and a finite family A(D) of ordered pairs of elements of V(D) called arcs (or directed edges). We call V(D) the vertex-set and A(D) the arc-family of D. An arc (v, w) is usually abbreviated to vw. Thus in Fig. 1.39, V(D) is the set {u, v, w, z} and A(D) consists of the arcs uv, vv, vw (twice), wv, wu and zw, with the ordering of the vertices in an arc indicated by an arrow. If D is a digraph, the graph obtained from D by 'removing the arrows' (that is, by replacing each arc of the form vw by a corresponding edge vw) is the underlying graph of D (see Fig. 1.40). Figure 1.39 Figure 1.40 D is a simple digraph if the arcs of D are all distinct, and if there are no 'loops' (arcs of the form vv). Note that the underlying graph of a simple digraph need not be a simple graph (see Fig. 1.41). We can imitate many of the definitions given in Section 1.1 for graphs. For example, two digraphs are isomorphic if there is an isomorphism between their underlying graphs that preserves the ordering of the vertices in each arc. Note that the digraphs in Figs 1.39 and 1.42 are not isomorphic. Figure 1.41 Figure 1.42
1.3 Variations on a theme 23 We can also define connectedness. A digraph D is (weakly) connected if it cannot be expressed as the union of two digraphs, defined in the obvious way. This is equivalent to saying that the underlying graph of D is a connected graph. A stronger definition of connectedness for digraphs will be given in Section 2.1. Two vertices v and w of a digraph D are adjacent if there is an arc in A(D) of the form vw or wv, and the vertices v and w are incident with such an arc. The out-degree of a vertex v of D is the number of arcs of the form vw, and is denoted by outdeg(v). Similarly, the in-degree of v is the number of arcs of D of the form wv, and is denoted by indeg(v). There is a digraph version of Theorem 1.1, which we call, naturally enough, the handshaking dilemma! THEOREM 1.3 (Handshaking dilemma) In any digraph the sum of all the outdegrees is equal to the sum of all the in-degrees. Proof. The sum of all the out-degrees is equal to the number of arcs, since each arc contributes exactly 1 to the sum. Similarly, the sum of all the in-degrees is equal to the number of arcs. ■ If D is a digraph without loops, with vertices labelled {1, 2, . . . , n}, its adjacency matrix A is the n ¥ n matrix whose ijth entry is the number of arcs from vertex i to vertex j. Figure 1.43 shows a labelled digraph with its adjacency matrix. Figure 1.43 An important type of digraph is a tournament. This is a digraph in which any two vertices are joined by exactly one arc (see Fig. 1.44). Note that its underlying graph is a complete graph. Such a digraph can be used to record the result of a tennis tournament or of any other game in which draws are not allowed. In Fig. 1.44, for example, team z beats team w, but is beaten by team v, and so on. Figure 1.44
24 Definitions and examples Infinite graphs An infinite graph G consists of an infinite set V(G ) of elements called vertices and an infinite family E(G) of unordered pairs of elements of V(G) called edges. If V(G) and E(G ) are both countably infinite (that is, they can be labelled 1, 2, 3, . . . ), then G is a countable graph. For convenience, we exclude the possibility of V(G) being infinite but E(G) finite, as such objects are merely finite graphs together with infinitely many isolated vertices, or of E(G) being infinite but V(G ) finite, as such objects are essentially finite graphs but with infinitely many loops or multiple edges. Many of our earlier definitions extend immediately to infinite graphs. The degree of a vertex v of an infinite graph is the cardinality of the set of edges incident with v, and may be finite or infinite. An infinite graph is locally finite if each of its vertices has finite degree; two important examples are the infinite square lattice and the infinite triangular lattice, shown in Figs 1.45 and 1.46. We similarly define a locally countable infinite graph to be one in which each vertex has countable degree. Figure 1.45 Figure 1.46 We can now prove the following simple, but fundamental, result. THEOREM 1.4 Every connected locally countable infinite graph is a countable graph. Proof. Let v be any vertex of such an infinite graph, and let A1 be the set of vertices adjacent to v, A2 be the set of all vertices adjacent to a vertex of A1, and so on. By hypothesis, A1 is countable, and hence so are A2, A3, . . . , since the union of a countable collection of countable sets is countable. Hence {v}, A1 A2, . . . is a sequence of sets whose union is countable and contains every vertex of the infinite graph, by connectedness. The result follows. ■ COROLLARY 1.5 Every connected locally finite infinite graph is a countable graph.
1.3 Variations on a theme 25 Exercises 1.35s Write down the vertex-set and arc-set of the digraph in Fig. 1.41. 1.36 Write down the vertex-set and arc-family of the graph in Fig. 1.42. 1.37s Two of the digraphs in Fig. 1.47 are isomorphic. Which two are they? Figure 1.47 1.38 Two of the digraphs in Fig. 1.48 are isomorphic. Which two are they? Figure 1.48 1.39s Verify the handshaking dilemma for the digraph of Fig. 1.39. 1.40 Verify the handshaking dilemma for the tournament of Fig. 1.49. Figure 1.49 1.41s Write down the adjacency matrix of the digraph in Fig. 1.39. 1.42 Write down the adjacency matrix of the tournament in Fig 1.44. 1.43 The converse D¢ of a digraph D is obtained from D by reversing the direction of each arc. (i) Give an example of a digraph that is isomorphic to its converse. (ii) What is the connection between the adjacency matrices of D and D¢? 1.44 Let T be a tournament on n vertices. If ∑ denotes a summation over all the vertices of T, prove that ∑ outdeg(v)2 = ∑ indeg(v)2. 1.45s Give an example of each of the following: (i) an infinite bipartite graph; (ii) an infinite connected cubic graph.
26 Definitions and examples 1.46 Give an example of each of the following: (i) an infinite graph with infinitely many end-vertices; (ii) an infinite graph with uncountably many vertices and edges. 1.4 Three puzzles In this section we present three recreational puzzles that can be solved using ideas relating to graphs. In each puzzle, notice how the use of a graph diagram makes the problem much easier to understand and to solve. The eight-circles problem Place the letters A, B, C, D, E, F, G, H into the eight circles in Fig. 1.50, in such a way that no letter is adjacent to a letter that is next to it in the alphabet. Figure 1.50 First note that trying all the possibilities is not feasible, as there are 8! = 40,320 ways of placing eight letters into eight circles. We therefore need a more systematic approach. Note that: (i) the easiest letters to place are A and H, because each has only one letter to which it cannot be adjacent (B and G, respectively); (ii) the hardest circles to fill are those in the middle, as each is adjacent to six others. This suggests that we place A and H in the middle circles. If we place A to the left of H, then the only possible positions for B and G are as shown in Fig. 1.51. Figure 1.51 The letter C must now be placed on the left-hand side of the diagram, and F must be placed on the right-hand side. It is then a simple matter to place the remaining letters, as shown in Fig. 1.52.
1.4 Three puzzles 27 Figure 1.52 Six people at a party Show that, in any gathering of six people, there are either three people who all know each other, or three people none of whom knows either of the other two. To solve this, we draw a graph in which we represent each person by a vertex, and join two vertices by a solid edge if the corresponding people know each other and by a dotted edge if not. We must show that there is always a solid triangle or a dotted triangle. Let v be any vertex. Then there must be exactly five edges incident with v, either solid or dotted, and so at least three of these edges must be of the same type. Let us assume that there are three solid edges (see Fig. 1.53); the case of at least three dotted edges is similar. Figure 1.53 If the people corresponding to the vertices w and x know each other, then v, w and x form a solid triangle, as required. Similarly, if the people corresponding to the vertices w and y, or to the vertices x and y, know each other, then we again obtain a solid triangle. These three cases are shown in Fig. 1.54. Figure 1.54
28 Definitions and examples Finally, if no two of the people corresponding to the vertices w, x and y know each other, then w, x and y form a dotted triangle, as required (see Fig. 1.55). Figure 1.55 Since this exhausts all possibilities, the result follows. The four-cubes problem We conclude this section with a puzzle that has long been popular under the name of 'Instant Insanity'. Given four cubes whose faces are coloured red, blue, green and yellow, as in Fig. 1.56, can we pile them up so that all four colours appear on each side of the resulting 4 ¥ 1 stack? Figure 1.56 Although these cubes can be stacked in thousands of different ways, there is essentially only one way that gives a solution. To solve this problem, we represent each cube by a graph with four vertices, R, B, G and Y, one for each colour. In each of these graphs, two vertices are adjacent if and only if the cube in question has the corresponding colours on opposite faces. The graphs corresponding to the cubes of Fig. 1.56 are shown in Fig. 1.57. Figure 1.57
1.4 Three puzzles 29 We next superimpose these graphs to form a new graph G (see Fig. 1.58). Figure 1.58 A solution of the puzzle is obtained by finding two subgraphs, H1 and H2, of G. The subgraph H1 tells us which pair of colours appear on the front and back of each cube, and the subgraph H2 tells us which pair of colours appear on the left and right. To this end, the subgraphs H1 and H2 must have the following properties: (a) Each subgraph contains exactly one edge from each cube: this ensures that each cube has a front and back, and a left and right, and the subgraphs tell us which pairs of colours appear on these faces. (b) The subgraphs have no edges in common: this ensures that the faces on the front and back are different from those on the sides. (c) Each subgraph is regular of degree 2: this tells us that each colour appears exactly twice on the sides of the stack (once on each side) and exactly twice on the front and back (once on the front and once on the back). Using these observations, we can easily check that neither loop can be included in the subgraphs. It then follows, after a little experimentation, that the subgraphs are as shown in Fig. 1.59, and the solution can then be read from them, as in Fig. 1.60. Figure 1.59 Figure 1.60
30 Definitions and examples Exercises 1.47s Find another solution of the eight-circles problem. 1.48s Show that there is a gathering of five people in which there are no three people who all know each other, and no three people none of whom knows either of the other two. 1.49s Find a solution of the four-cubes problem for the set of cubes in Fig. 1.61. Figure 1.61 1.50 Show that the four-cubes problem in Fig. 1.62 has no solution. Figure 1.62 Challenge problems 1.51 A simple graph that is isomorphic to its complement is self-complementary. (i) Prove that, if G is self-complementary, then G has 4k or 4k + 1 vertices, where k is an integer. (ii) Find all self-complementary graphs with four and five vertices. (iii) Find a self-complementary graph with eight vertices. 1.52 ( For those who know linear algebra) If G is a simple graph with edge-set E(G), the vector space of G is the vector space over the field Z2 = {0, 1} of integers modulo 2, whose elements are subsets of E(G). The sum E + F of two such subsets E and F is the set of edges in E or F but not both, and scalar multiplication is defined by 1.E = E and 0.E = Ø. Show that this defines a vector space over Z2, and find a basis for it. 1.53 The line graph L(G ) of a simple graph G is the graph whose vertices are in one–one correspondence with the edges of G, with two vertices of L(G) being adjacent if and only if the corresponding edges of G are adjacent. (i) Show that K3 and K1,3 have the same line graph. (ii) Show that the line graph of the tetrahedron graph is the octahedron graph. (iii) Prove that, if G is regular of degree k, then L(G) is regular of degree 2k - 2. (iv) Find an expression for the number of edges of L(G) in terms of the degrees of the vertices of G. (v) Show that L(K5) is the complement of the Petersen graph.
1.4 Three puzzles 31 1.54 (For those who know group theory) An automorphism j of a simple graph G is a one–one mapping of the vertex-set of G onto itself with the property that j(v) and j(w) are adjacent whenever v and w are. The automorphism group G(G) of G is the group of automorphisms of G under composition. (i) Prove that the groups G(G ) and G(ı) are isomorphic. (ii) Find the groups G(Kn), G(Kr,s) and G(Cn). (iii) Use the results of parts (i) and (ii) and of Exercise 1.53(v) to find the automorphism group of the Petersen graph. 1.55 Show that an infinite graph G can be drawn in Euclidean 3-space if V(G) and E(G) can each be put in one–one correspondence with a subset of the set of real numbers. 1.56 Prove that the solution of the four-cubes problem in the text is the only solution for that set of cubes.
Chapter 2 Paths and cycles So many paths that wind and wind, While just the art of being kind Is all the sad world needs. Ella Wheeler Wilcox Now that we have a reasonable armoury of graphs, we can look at their properties. To do this, we need some definitions that describe ways of 'going from one vertex to another', in both graphs and digraphs. We give these definitions in Section 2.1 and present some results on connectivity. In Sections 2.2 and 2.3 we study two particular types of graph and digraph: those with trails that include every edge, and those with cycles that pass through every vertex. We conclude this chapter, in Section 2.4, with some applications of paths and cycles. 2.1 Connectivity Given a graph G, a walk in G is a finite sequence of edges of the form v0v1, v1v2, . . . , vm-1vm, also denoted by v0 2 v1 2 v2 2 · · · 2 vm, in which any two consecutive edges are adjacent or identical. Such a walk determines a sequence of vertices v0, v1, . . . , vm. We call v0 the initial vertex and vm the final vertex of the walk, and speak of a walk from v0 to vm. The number of edges in a walk is called its length; for example, in Fig. 2.1, v2w2x2y2z2z2y2w is a walk of length 7 from v to w. Figure 2.1
2.1 Connectivity 33 The concept of a walk is usually too general for our purposes, so we impose some restrictions. A walk in which all the edges are distinct is a trail. If, in addition, the vertices v0, v1, . . . , vm are distinct (except, possibly, v0 = vm), then the trail is a path. A walk, path or trail is closed if v0 = vm, and a closed path with at least one edge is a cycle. For example, and v 2 w 2 x 2 y 2 z 2 z 2 x is a trail, v 2 w 2 x 2 y 2 z is a path, v 2 w 2 x 2 y 2 z 2 x 2 v is a closed trail, v 2 w 2 x 2 y 2 v is a cycle. Note that a loop is a cycle of length 1, and a pair of multiple edges is a cycle of length 2. A cycle of length 3, such as v 2 w 2 x 2 v, is called a triangle. Figure 2.2 We observe that a graph is connected if and only if there is a path between each pair of vertices (see Fig. 2.2). We can also prove the following results on bipartite graphs: THEOREM 2.1 A graph G is bipartite if and only if every cycle of G has even length. Proof. 7 If G is bipartite, we can split its vertex-set into two disjoint sets A and B so that each edge of G joins a vertex of A and a vertex of B. Let v0 2 v1 2 · · · 2 vm 2 v0 be a cycle in G, and assume (without loss of generality) that v0 is in A. Then v1 is in B, v2 is in A, v3 is in B, and so on. Since vm must be in B, the cycle has even length. 6 Conversely, assume that every cycle of G has even length. We may assume that G is connected. Choose any vertex v, let A be the set of vertices w for which the shortest path from v to w has even length, and let B be the set of vertices not in A. If any two vertices of A (or of B) were adjacent, then the shortest paths from these vertices to v would include a cycle of odd length. Thus each edge of G must join a vertex of A and a vertex of B, so G is bipartite. ■
34 Paths and cycles We next investigate bounds on the number of edges of a simple connected graph with n vertices. Such a graph has fewest edges when it has no cycles, and has most edges when it is a complete graph; this implies that the number of edges must lie between n - 1 and 1/2 n(n - l). In fact, we can prove a stronger result that includes this as a special case. THEOREM 2.2 Let G be a simple graph on n vertices. If G has k components, then the number m of edges of G satisfies n - k ≤ m ≤ 1/2(n - k)(n - k + 1). Proof. We prove the lower bound m ≥ n - k by induction on the number of edges of G, the result being trivial if G is a null graph. If G contains as few edges as possible (say m0), then the removal of any edge of G must increase the number of components by 1, and the graph that remains has n vertices, k + 1 components and m0 - 1 edges. It follows from the induction hypothesis that m0 - 1 ≥ n - (k + 1), giving m0 ≥ n - k, as required. To prove the upper bound, we can assume that each component of G is a complete graph. Suppose, then, that there are two components Ci and Cj with ni and nj vertices, respectively, where ni ≥ nj > 1. If we now replace Ci and Cj by complete graphs on ni + 1 and nj - 1 vertices, then the total number of vertices remains unchanged, but the number of edges is changed by 1 /2{(ni + 1)ni - ni(ni - 1)} - 1/2{nj(nj - 1) - (nj - 1)(nj - 2)} = ni - nj + 1, which is positive. It follows that, in order to attain the maximum number of edges, G must consist of a complete graph with n - k + 1 vertices and k - 1 isolated vertices. The result now follows. ■ We deduce the following corollary (see Exercise 2.4): COROLLARY 2.3 Any simple graph with n vertices and more than 1/2(n - 1)(n - 2) edges is connected. Connectivity Another approach used in the study of connected graphs is to ask 'how connected is a given graph?'. Such questions have arisen in connection with the vulnerability of certain networks, such as a rail or telecommunication network. One interpretation of this is to ask how many edges (railway lines or telephone cables) or vertices (stations or telephone exchanges) need to be out of action for the network to become disconnected. We now introduce some terms that are useful when discussing such questions. A disconnecting set in a connected graph G is a set of edges whose deletion disconnects G. For example, in the graph of Fig. 2.3, the sets {e1, e2, e5} and {e3, e6, e7, e8} are disconnecting sets of G; the disconnected graph left after deletion of the second is shown in Fig. 2.4.
2.1 Connectivity 35 Figure 2.3 Figure 2.4 We further define a cutset to be a minimal disconnecting set – that is, a disconnecting set, no proper subset of which is a disconnecting set; in the above example, only the second disconnecting set is a cutset. Note that the deletion of the edges in a cutset always leaves a graph with exactly two components. If a cutset has only one edge e, we call e a bridge (see Fig. 2.5). Figure 2.5 These definitions can easily be extended to disconnected graphs. If G is any such graph, a disconnecting set of G is a set of edges whose removal increases the number of components of G, and a cutset of G is a minimal disconnecting set. If G is connected, its edge-connectivity l(G ) is the size of the smallest cutset in G. Thus l(G) is the smallest number of edges that we need to delete in order to disconnect G. For example, if G is the graph of Fig. 2.3, then l(G) = 2, corresponding to the cutset {e1, e2}. We also say that G is k-edge-connected if l(G) ≥ k. Thus the graph of Fig. 2.3 is l-edge-connected and 2-edge-connected, but is not 3-edge-connected. It can be proved that a graph is 2-edge-connected if and only if any two distinct vertices are joined by at least two paths with no edges in common (see Exercise 2.8(i)); for example, any two distinct vertices of Fig. 2.3 are joined by at least two such paths. More generally we have the following celebrated theorem of K. Menger. It will be proved in Chapter 6. THEOREM 2.4 (Menger, 1927) A graph G is k-edge-connected if and only if any two distinct vertices of G are joined by at least k paths, no two of which have any edges in common. We can also define the analogous concepts for the removal of vertices. A separating set in a connected graph G is a set of vertices whose deletion disconnects G; recall that when we delete a vertex, we must also remove its incident edges. For example, in the graph of Fig. 2.3, the sets {w, x} and {w, x, y} are separating sets of G; the disconnected graph left after removal of the first is shown in Fig. 2.6. If a separating set contains only one vertex v, we call v a cut-vertex (see Fig. 2.7). These definitions extend immediately to disconnected graphs, as above.
36 Paths and cycles Figure 2.6 Figure 2.7 If G is connected and not a complete graph, its (vertex) connectivity k(G) is the size of the smallest separating set in G. Thus k(G ) is the smallest number of vertices that we need to delete in order to disconnect G. For example, if G is the graph of Fig. 2.3, then k(G) = 2, corresponding to the separating set {w, x}. We also say that G is k-connected if k(G) ≥ k. Thus the graph of Fig. 2.3 is 1-connected and 2-connected, but is not 3-connected. It can be proved that a graph with at least three vertices is 2-connected if and only if any two distinct vertices are joined by at least two paths with no other vertices in common; for example, any two distinct vertices of Fig. 2.3 are joined by at least two such paths (see Exercise 2.8(ii)). More generally, we have another theorem of Menger, which will also be proved in Chapter 6. THEOREM 2.5 (Menger, 1927) A graph G with at least k + 1 vertices is k-connected if and only if any two vertices of G are joined by at least k paths, no two of which have any other vertices in common. These concepts are not unrelated. For example, it can be proved that, if G is any connected graph, then k(G) ≤ l(G ) ≤ d(G), where d(G) is the smallest vertex-degree in G. As we shall see, there are striking and unexpected similarities between the properties of cycles and cutsets; for example, look at Exercises 2.46, 2.47, 2.48, 2.49 and Theorem 3.2. The reasons for these similarities will become clear in Chapter 7. Digraphs There are also natural generalizations to digraphs of the above definitions. A walk in a digraph D is a finite sequence of arcs of the form v0v1, v1v2, . . . , vm-1vm. We sometimes write this sequence as v0 2 v1 2 · · · 2 vm, and speak of a walk from v0 to vm. In an analogous way, we can define directed trails, directed paths and directed cycles (or, simply, trails, paths and cycles, when there is no possibility of confusion). Note that although a trail cannot contain a given arc vw more than once, it can contain both vw and wv; for example, in Fig. 2.8, z2w2v2w2u is a trail.
2.1 Connectivity 37 Figure 2.8 We can also define connectedness. The two most useful types of connected digraph correspond to whether or not we take account of the directions of the arcs: these definitions are the natural extensions to digraphs of the two descriptions of connected graphs in Sections 1.2 and 2.1. We have already defined a digraph D to be connected if it cannot be expressed as the union of two digraphs; this is equivalent to saying that the underlying graph of D is a connected graph. We also say that D is strongly connected if, for any two vertices v and w of D, there is a directed path from v to w. Every strongly connected digraph is connected, but not all connected digraphs are strongly connected; for example, the connected digraph of Fig. 2.8 is not strongly connected, since there is no path from v to z. The distinction between a connected digraph and a strongly connected one becomes more evident if we consider the road map of a city, all of whose streets are one way. If the road map is connected, then we can drive from any part of the city to any other, ignoring the directions of the one-way streets as we go. However, if the map is strongly connected, then we can drive from any part of the city to any other, always going the 'right way' down the one-way streets. Since every one-way system needs to be strongly connected, it is natural to ask when we can impose a one-way system on a street map so that we can drive from any part of the city to any other. This is not always possible: for example, if the city consists of two parts connected by a single bridge, then we cannot impose such a one-way system on the city, since whatever direction we give to the bridge, one part of the city is cut off. But if there are no bridges, then we can always impose such a one-way system. This result is stated below in Theorem 2.6. For convenience, we define a graph G to be orientable if each edge of G can be directed so that the resulting digraph is strongly connected; such a digraph is an orientation of G. For example, if G is the graph shown in Fig. 2.9, then G is orientable; an orientation is shown in Fig. 2.10. Figure 2.9 Figure 2.10
38 Paths and cycles The following theorem gives a necessary and sufficient condition (due to H. E. Robbins) for a graph to be orientable. THEOREM 2.6 A connected graph G is orientable if and only if each edge of G lies in at least one cycle. Proof. The necessity of the condition is clear. To prove the sufficiency, we choose any cycle C and direct its edges cyclically. If each edge of G is contained in C, then the proof is complete. If not, we choose any edge e that is not in C but which is adjacent to an edge of C. By hypothesis, e is contained in some cycle C ¢ whose edges we may direct cyclically, except for those edges that have already been directed – that is, those edges of C¢ that also lie in C; the situation is illustrated in Fig. 2.11, with dotted lines denoting edges of C¢. We proceed in this way, at each stage directing at least one new edge, until all edges have been directed. Since the digraph must remain strongly connected at each stage of the process, the result follows. ■ Figure 2.11 Infinite graphs We can also extend the concept of a walk to an infinite graph G. There are essentially three different types of walk in G: (i) a finite walk is defined exactly as above; (ii) a one-way infinite walk with initial vertex v0 is an infinite sequence of edges of the form v0 2 v1 2 v2 2 · · · ; (iii) a two-way infinite walk is an infinite sequence of edges of the form · · · 2 v-2 2 v-1 2 v0 2 v1 2 v2 2 · · · . One-way and two-way infinite trails and paths are defined analogously. The following result, known as König's lemma, tells us that infinite paths are not difficult to come by; we shall use this result in Chapter 4. THEOREM 2.7 (König, 1927) Let G be a connected locally finite infinite graph. Then, for any vertex v of G, there exists a one-way infinite path with initial vertex v.
2.1 Connectivity 39 Proof. For each vertex z other than v, there is a non-trivial path from v to z. It follows that there are infinitely many paths in G with initial vertex v. Since the degree of v is finite, infinitely many of these paths must start with the same edge. If vv1 is such an edge, then we can repeat this procedure for the vertex v1 and thus obtain a new vertex v2 and a corresponding edge v1v2. By carrying on in this way, we obtain the one-way infinite path v 2 v1 2 v2 2 · · · . ■ Exercises 2.1s In the Petersen graph, find (i) a trail of length 5; (ii) a path of length 9; (iii) cycles of lengths 5, 6, 8 and 9; (iv) cutsets with three, four and five edges. 2.2 In the dodecahedron graph, find (i) a trail of length 5; (ii) a path of length 10; (iii) cycles of lengths 5, 8 and 9; (iv) cutsets with three, four and five edges. 2.3s The girth of a graph is the length of its shortest cycle. Write down the girths of the following graphs: (i) K9; (ii) K5,7; (iii) C8; (iv) W8; (v) Q5; (vi) the Petersen graph; (vii) the graph of the dodecahedron. 2.4 Prove Corollary 2.3. 2.5s Prove that a simple graph and its complement cannot both be disconnected. 2.6s Write down k(G ) and l(G) for each of the following graphs G: (i) C6; (ii) W6; (iii) K4,7; (iv) Q4. 2.7 (i) Show that, if G is a connected graph with minimum degree k, then l(G) ≤ k. (ii) Draw a graph G with minimum degree k for which k(G) < l(G ) < k. 2.8 (i) Prove that a graph is 2-edge-connected if and only if any two distinct vertices are joined by at least two paths with no edges in common. (ii) Prove that a graph with at least three vertices is 2-connected if and only if any two distinct vertices are joined by at least two paths with no other vertices in common. 2.9 In a connected graph, the distance d(v, w) between a vertex v and a vertex w is the length of the shortest path from v to w. (i) If d(v, w) ≥ 2, show that there exists a vertex z such that d(v, z) + d(z, w) = d(v, w). (ii) In the Petersen graph, show that d(v, w) = 1 or 2, for any distinct vertices v and w.
40 Paths and cycles 2.10 Show, by finding an orientation for each, that Kn (n ≥ 3) and Kr, s (r, s ≥ 2) are orientable. 2.11 Find orientations for the Petersen graph and the graph of the dodecahedron. 2.12 A tournament is transitive if the existence of arcs uv and vw implies the existence of an arc uw. (i) Give an example of a transitive tournament. (ii) Show that in a transitive tournament the teams can be ranked so that each team beats all the teams which follow it in the ranking. (iii) Deduce that a transitive tournament with at least two vertices cannot be strongly connected. 2.13 A tournament T is irreducible if it is impossible to split the set of vertices of T into two disjoint sets V1 and V2 so that each arc joining a vertex of V1 and a vertex of V2 is directed from V1 to V2. (i) Give an example of an irreducible tournament. (ii) Prove that a tournament is irreducible if and only if it is strongly connected. 2.14s Give an example to show that the conclusion of König's lemma is false if we omit the condition that the infinite graph is locally finite. 2.2 Eulerian graphs and digraphs In this section we consider Eulerian graphs and digraphs. The name 'Eulerian' arises from the fact that in 1735 the Swiss mathematician Leonhard Euler solved the famous Königsberg bridges problem which asks whether you can cross each of the seven bridges in Fig. 2.12 exactly once and return to your starting point. This is equivalent to asking whether the graph in Fig. 2.13 has an 'Eulerian trail' (as defined below), although Euler did not rephrase the problem in this way. Figure 2.12 Figure 2.13 A translation of Euler's paper, and a discussion of various related topics, may be found in Biggs, Lloyd and Wilson [17]. Problems on Eulerian graphs frequently appear in books on recreational mathematics. A typical problem might ask whether a given diagram, such as that in Fig. 2.13, can be drawn without lifting one's pencil from the paper and without repeating any lines.
2.2 Eulerian graphs and digraphs 41 Eulerian graphs A connected graph G is Eulerian if there exists a closed trail that includes every edge of G; such a trail is an Eulerian trail. Note that this definition requires you to traverse each edge once and once only, and to finish at your starting point. A nonEulerian graph G is semi-Eulerian if there exists a (non-closed) trail that includes every edge of G. Figures 2.14, 2.15 and 2.16 show graphs that are Eulerian, semiEulerian and non-Eulerian, respectively. Figure 2.14 Figure 2.15 Figure 2.16 One question that immediately arises is 'are there necessary and sufficient conditions for a graph to be Eulerian?' Before answering this question in Theorem 2.9, we prove a simple lemma. LEMMA 2.8 If G is a graph in which the degree of each vertex is at least 2, then G contains a cycle. Proof. If G has any loops or multiple edges, the result is trivial. We can therefore suppose that G is a simple graph. Let v be any vertex of G. We construct a walk v 2 v1 2 v2 2 · · · inductively, by choosing v1 to be any vertex adjacent to v and, for each i > 1, choosing vi+1 to be any vertex adjacent to vi except vi-1; the existence of such a vertex is guaranteed by our hypothesis. Since G has only finitely many vertices, we must eventually choose a vertex that has been chosen before. If vk is the first such vertex, then the part of the walk that lies between the two occurrences of vk is the required cycle. ■ We come now to the main result of this section, which tells us that a given connected graph is Eulerian if and only if all of its vertex-degrees are even. In terms of the Königsberg bridges problem, this corresponds to a city map in which the number of bridges that emerge from each part of the city is even. THEOREM 2.9 (Euler, 1735) A connected graph G is Eulerian if and only if the degree of each vertex of G is even. Proof. 7 Suppose that P is an Eulerian trail of G. Whenever P passes through a vertex, there is a contribution of 2 towards the degree of that vertex. Since each edge
42 Paths and cycles occurs exactly once in P, the degree of each vertex must be a sum of 2s, and is thus an even number. 6 The proof is by induction on the number of edges of G. Suppose that the degree of each vertex is even. Since G is connected, each vertex has degree at least 2 and so, by Lemma 2.8, G contains a cycle C. If C contains every edge of G, the proof is complete. If not, we remove from G the edges of C to form a new (possibly disconnected) graph H with fewer edges than G, and in which each vertex still has even degree. By the induction hypothesis, each component of H has an Eulerian trail. But each component of H has at least one vertex in common with C, by connectedness. It follows that we can obtain the required Eulerian trail of G by tracing the edges of C until a non-isolated vertex of H is reached, tracing the Eulerian trail of the component of H that contains that vertex, and then continuing along the edges of C until we reach a vertex belonging to another component of H, and so on. The whole process terminates when we return to the initial vertex (see Fig. 2.17). ■ Figure 2.17 This proof can easily be modified to prove the following two results; we omit the details (see Exercise 2.18). COROLLARY 2.10 A connected graph is Eulerian if and only if its set of edges can be split up into edge-disjoint cycles. COROLLARY 2.11 A connected graph is semi-Eulerian if and only if it has exactly two vertices of odd degree. Note that, in a semi-Eulerian graph, any semi-Eulerian trail must have one vertex of odd degree as its initial vertex and the other as its final vertex. Note also that, by the handshaking lemma, a graph cannot have exactly one vertex of odd degree. We conclude our introduction to Eulerian graphs with an algorithm for constructing an Eulerian trail in a given Eulerian graph. The method is known as Fleury's algorithm.
2.2 Eulerian graphs and digraphs 43 THEOREM 2.12 Let G be an Eulerian graph. Then the following construction is always possible, and produces an Eulerian trail of G. Start at any vertex u and traverse the edges in an arbitrary manner, subject only to the following rules: (i) erase the edges as they are traversed, and if any isolated vertices result, erase them too; (ii) at each stage, use a bridge only if there is no alternative. Proof. We show first that the construction can be carried out at each stage. Suppose that we have just reached a vertex v, erasing the edges as we go. If v ≠ u, then the subgraph H that remains is connected and has only two vertices of odd degree, u and v. To show that the construction can be carried out, we must show that the removal of the next edge does not disconnect H – or, equivalently, that v is incident with at most one bridge. But if this is not the case, then there exists a bridge vw such that the component K of H - vw containing w does not contain u (see Fig. 2.18). Since the vertex w has odd degree in K, some other vertex of K must also have odd degree, giving the required contradiction. If v = u, the proof is almost identical, as long as there are still edges incident with u. Figure 2.18 It remains only to show that this construction always yields a complete Eulerian trail. But this is clear, since no edges of G can remain untraversed when the last edge incident with u is used, since otherwise the removal of some earlier edge adjacent to one of these edges would have disconnected the graph, contradicting (ii). ■ Eulerian digraphs We can also obtain digraph analogues of some of the above results. A connected digraph D is Eulerian if there exists a closed directed trail that includes every arc of D; such a trail is an Eulerian trail. For example, the digraph in Fig. 2.19 is not Eulerian, even though its underlying graph is an Eulerian graph.
44 Paths and cycles Figure 2.19 Note that the digraph must be strongly connected for an Eulerian trail to exist. Note also that any Eulerian graph is orientable, since we simply follow any Eulerian trail, directing the edges in the direction of the trail as we go. Our first aim is to give a necessary and sufficient condition, analogous to the one in Theorem 2.9, for a connected digraph to be Eulerian. THEOREM 2.13 A strongly connected digraph is Eulerian if and only if, for each vertex v of D, outdeg(v) = indeg(v). Proof. The proof is entirely analogous to that of Theorem 2.9, and is left as an exercise. ■ We leave it to you to define a semi-Eulerian digraph, and to obtain digraph analogues of Corollaries 2.10 and 2.11 (see Exercise 2.23). Infinite Eulerian graphs We conclude this section with a brief discussion of infinite Eulerian graphs. It seems natural to call a connected infinite graph G Eulerian if there exists a two-way infinite trail that includes every edge of G; such an infinite trail is a two-way Eulerian trail. Note that these definitions require G to be countable. The following theorems give further necessary conditions for an infinite graph to be Eulerian. THEOREM 2.14 Let G be a countable connected graph which is Eulerian. Then (i) G has no vertices of odd degree; (ii) for each finite subgraph H of G, the infinite graph K obtained by deleting from G the edges of H has at most two infinite components; (iii) if, in addition, each vertex of H has even degree, then K has exactly one infinite component. Proof. (i) Suppose that P is an Eulerian trail. Then, by the argument given in the proof of Theorem 2.9, each vertex of G must have either even or infinite degree.
2.2 Eulerian graphs and digraphs 45 (ii) Let P be split up into three subtrails P-, P0 and P+ in such a way that P0 is a finite trail containing every edge of H (and possibly other edges as well), and P- and P+ are one-way infinite trails. Then the infinite graph formed by the edges of P- and P+, and the vertices incident with them, has at most two infinite components. Since K is obtained by adding only a finite set of edges to this graph, the result follows. (iii) Let the initial and final vertices of P0 be v and w. We wish to show that v and w are connected in K. If v = w, this is obvious. If not, then the result follows when we apply Corollary 2.11 to the graph obtained by removing the edges of H from P0, this graph having exactly two vertices (v and w) of odd degree, by hypothesis. ■ The necessary conditions given in the previous theorem are also sufficient. We state this result formally in the following theorem. Its proof may be found in Ore [15]. THEOREM 2.15 If G is a connected countable graph, then G is Eulerian if and only if conditions (i), (ii) and (iii) of Theorem 2.14 are satisfied. Exercises 2.15s Which of the following graphs are Eulerian or semi-Eulerian? (i) the complete graph K5; (ii) the complete bipartite graph K2,3; (iii) the graph of the cube; (iv) the graph of the octahedron; (v) the Petersen graph. 2.16s In the table of Fig. 1.9, locate all the Eulerian and semi-Eulerian graphs. 2.17 (i) (ii) (iii) (iv) (v) 2.18 Prove Corollaries 2.10 and 2.11. For which values of n is Kn Eulerian? Which complete bipartite graphs are Eulerian? Which Platonic graphs are Eulerian? For which values of n is the wheel Wn Eulerian? For which values of k is the k-cube Qk Eulerian? 2.19s Let G be a connected graph with k (> 0) vertices of odd degree. (i) Show that the minimum number of trails, that together include every edge of G and that have no edges in common, is 1/2 k. (ii) How many continuous pen-strokes are needed to draw the diagram in Fig. 2.20 without repeating any line? Figure 2.20
46 Paths and cycles 2.20s Use Fleury's algorithm to produce an Eulerian trail for the graph in Fig. 2.21. Figure 2.21 2.21 An Eulerian graph is randomly traceable from a vertex v if, whenever we start from v and traverse the graph in an arbitrary way never using any edge twice, we eventually obtain an Eulerian trail. (i) Show that the graph in Fig. 2.22 is randomly traceable. Figure 2.22 (ii) Give an example of an Eulerian graph that is not randomly traceable. (iii) Why might a randomly traceable graph be suitable for the layout of an exhibition? 2.22s Find an Eulerian trail in the tournament of Fig. 2.23. Figure 2.23 2.23 Prove Theorem 2.13 and the digraph analogues of Corollaries 2.10 and 2.11. 2.24 Let D be the digraph whose vertices are the pairs of integers 11, 12, 13, 21, 22, 23, 31, 32, 33, and whose arcs join ij to kl if and only if j = k. Find an Eulerian trail in D and
2.3 Hamiltonian graphs and digraphs 47 use it to obtain a circular arrangement of nine 1s, nine 2s and nine 3s in which each of the 27 possible triples (111, 233, etc.) occurs exactly once. (Problems of this kind arise in communication theory.) 2.25 (i) Find an Eulerian trail in the infinite square lattice S. (ii) Verify that S satisfies the conditions of Theorem 2.14. 2.26 Repeat Exercise 2.25 for the infinite triangular lattice. 2.3 Hamiltonian graphs and digraphs In the previous section we discussed whether there exists a closed trail that includes every edge of a given connected graph G. A similar problem is to determine whether there exists a closed trail passing exactly once through each vertex of G: such a trail must be a cycle, except when G is the graph K1. Such a cycle is a Hamiltonian cycle and a graph with a Hamiltonian cycle is a Hamiltonian graph. A non-Hamiltonian graph is semi-Hamiltonian if there exists a path through every vertex. Figures 2.24, 2.25 and 2.26 show graphs that are Hamiltonian, semi-Hamiltonian and nonHamiltonian, respectively. Figure 2.24 Figure 2.25 Figure 2.26 The name 'Hamiltonian cycle' arises from the fact that the Irish mathematician Sir William Hamilton investigated their existence in the dodecahedron graph in connection with a problem in algebra, although cycles on polyhedra in general had been studied earlier by the Revd. T. P. Kirkman. A cycle on a dodecahedron is shown with solid lines in Fig. 2.27. Figure 2.27 In Theorem 2.9 and Corollary 2.10 we obtained necessary and sufficient conditions for a connected graph to be Eulerian, and we may hope to obtain similar
48 Paths and cycles characterizations for Hamiltonian graphs – but no such characterization is known. In fact, little is known in general about Hamiltonian graphs, and most results have the form 'if G has enough edges, then G is Hamiltonian'. Probably the most celebrated of these is Dirac's theorem, due to G. A. Dirac (Corollary 2.17). We deduce it from the following more general result of O. Ore. THEOREM 2.16 (Ore, 1960) If G is a simple graph with n (≥ 3) vertices, and if deg(v) + deg(w) ≥ n for each pair of non-adjacent vertices v and w, then G is Hamiltonian. Proof. We assume that the result is false, and derive a contradiction. So let G be a non-Hamiltonian graph with n vertices, satisfying the given condition on the vertex degrees. By adding extra edges if necessary, we may assume that G is 'only just' non-Hamiltonian, in the sense that the addition of any further edge gives a Hamiltonian graph; note that adding an extra edge does not violate the condition on the vertex degrees. It follows that G contains a path v1 2 v2 2 · · · 2 vn passing through every vertex. But since G is non-Hamiltonian, the vertices v1 and vn are not adjacent, and so deg(v1) + deg(vn) ≥ n. It follows that there must be some vertex vi adjacent to v1 with the property that vi-1 is adjacent to vn (see Fig. 2.28). Figure 2.28 But this gives us the required contradiction since v1 2 v2 2 · · · 2 vi-1 2 vn 2 vn-1 2 · · · 2 vi+1 2 vi 2 v1 is then a Hamiltonian cycle. ■ COROLLARY 2.17 (Dirac, 1952) If G is a simple graph with n (≥ 3) vertices, and if deg(v) ≥ 1/2n for each vertex v, then G is Hamiltonian. Proof. The result follows immediately from Theorem 2.16, since deg(v) + deg(w) ≥ n for each pair of vertices v and w, whether adjacent or not. ■ Hamiltonian digraphs As we might expect, the study of Hamiltonian digraphs is less successful than that of Eulerian digraphs. A digraph D is Hamiltonian if there is a directed cycle that includes every vertex of D. A non-Hamiltonian digraph that contains a directed path through
2.3 Hamiltonian graphs and digraphs 49 every vertex is semi-Hamiltonian. Little is known about Hamiltonian digraphs, and several theorems on Hamiltonian graphs do not generalize easily, if at all, to digraphs. It is natural to ask whether there is a generalization to digraphs of Dirac's theorem (Corollary 2.17). One such generalization is due to M. A. Ghouila-Houri; its proof is more difficult than that of Dirac's theorem, and can be found in West [16]. THEOREM 2.18 Let D be a strongly connected digraph with n vertices. If outdeg(v) ≥ 1/2n and indeg(v) ≥ 1/2n for each vertex v, then D is Hamiltonian. It seems that such results will not come easily, and so we consider instead which types of digraph are Hamiltonian. In this respect, the tournaments are particularly important, the results in this case taking a very simple form. Because tournaments may have vertices with out-degree or in-degree 0, they are not in general Hamiltonian. However, the following theorem, due to L. Rédei and P. Camion, shows that every tournament is 'nearly Hamiltonian'. THEOREM 2.19 (i) Every non-Hamiltonian tournament is semi-Hamiltonian. (ii) Every strongly connected tournament is Hamiltonian. Proof. (i) The statement is clearly true if the tournament has fewer than four vertices. We prove the result by induction on the number of vertices, and assume that every non-Hamiltonian tournament on n vertices is semi-Hamiltonian. Let T be a non-Hamiltonian tournament on n + 1 vertices, and let T ¢ be the tournament on n vertices obtained by removing from T a vertex v and its incident arcs. By the induction hypothesis, T¢ has a semi-Hamiltonian path v1 2 v2 2 · · · 2 vn. There are now three cases to consider: ■ if vv1 is an arc in T, then the required path is v 2 v1 2 v2 2 · · · 2 vn. ■ if vv1 is not an arc in T (which means that v1v is), and if there exists an i such that vvi is an arc in T, then choosing i to be the first such, we obtain the required path (see Fig. 2.29) v1 2 v2 2 · · · 2 vi-1 2 v 2 vi 2 · · · 2 vn. Figure 2.29
50 Paths and cycles ■ if there is no arc in T of the form vvi, then the required path is v1 2 v2 2 · · · 2 vn 2 v. (ii) We prove the stronger result that a strongly connected tournament T on n vertices contains cycles of length 3, 4, . . . , n. To show that T contains a cycle of length 3, let v be any vertex of T, and let W be the set of all vertices w such that vw is an arc in T, and Z be the set of all vertices z such that zv is an arc. Since T is strongly connected, W and Z must both be nonempty, and there must be an arc in T of the form w¢z¢, where w¢ is in W and z¢ is in Z (see Fig. 2.30). The required cycle of length 3 is then v 2 w¢ 2 z¢ 2 v. Figure 2.30 It remains only to show that, if there is a cycle of length k, where k ≤ n, then there is one of length k + 1. Let v1 2 v2 2 · · · 2 vk 2 v1 be such a cycle. Suppose first that there exists a vertex v, not contained in this cycle, for which there exist arcs in T of the form vvi and of the form vjv. Then there must be a vertex vi such that both vi-1v and vvi are arcs in T. The required cycle is then (see Fig. 2.31) v1 2 v2 2 · · · 2 vi-1 2 v 2 vi 2 · · · 2 vk 2 v1. If no vertex exists with the above-mentioned property, then the set of vertices not contained in the cycle may be divided into two disjoint sets W and Z, where W is the set of vertices w such that viw is an arc for each i, and Z is the set of vertices z such Figure 2.31 Figure 2.32
2.3 Hamiltonian graphs and digraphs 51 that zvi is an arc for each i. Since T is strongly connected, W and Z must both be nonempty, and there must be an arc in T of the form w¢z¢, where w¢ is in W and z¢ is in Z. The required cycle is then (see Fig. 2.32) v1 2 w¢ 2 z¢ 2 v3 2 · · · 2 vk 2 v1. ■ Exercises 2.27s Which of the following graphs are Hamiltonian or semi-Hamiltonian? (i) the complete graph K5; (ii) the complete bipartite graph K2,3; (iii) the graph of the octahedron; (iv) the wheel W6; (v) the 4-cube Q4. 2.28s In the table of Fig. 1.9, locate all the Hamiltonian and semi-Hamiltonian graphs. 2.29 (i) (ii) (iii) (iv) (v) 2.30 Is the Grötzsch graph in Fig. 2.33 Hamiltonian? Figure 2.33 For which values of n is Kn Hamiltonian? Which complete bipartite graphs are Hamiltonian? Which Platonic graphs are Hamiltonian? For which values of n is the wheel Wn Hamiltonian? For which values of k is the k-cube Qk Hamiltonian? Figure 2.34 2.31 (i) Prove that, if G is a bipartite graph with an odd number of vertices, then G is non-Hamiltonian. (ii) Deduce that the graph in Fig. 2.34 is non-Hamiltonian. 2.32 Use the result of Exercise 2.31(i) to show that a knight cannot visit all the squares of a 5 ¥ 5 or 7 ¥ 7 chessboard exactly once by knight's moves and return to its starting point. Can a knight visit all the squares of a 6 ¥ 6 chessboard? 2.33s Give an example to show that the condition 'deg(v) ≥ 1/2 n', in the statement of Dirac's theorem, cannot be replaced by 'deg(v) ≥ 1/2(n - 1)'. 2.34 (i) Let G be a graph with n vertices and {1/2(n - 1)(n - 2)} + 2 edges. Use Ore's theorem to prove that G is Hamiltonian. (ii) Find a non-Hamiltonian graph with n vertices and {1/2(n - 1)(n - 2)} + 1 edges. 2.35s Find a Hamiltonian cycle in the tournament of Fig. 2.23.
52 Paths and cycles 2.4 Applications Many important advances in graph theory arose as a result of attempts to solve particular problems – Euler and the bridges of Königsberg (Section 2.2), Cayley and the enumeration of chemical molecules (Section 3.2), and Kirchhoff's work on electrical networks (Section 3.3), to name but three. Much present-day interest in the subject is due to the fact that, quite apart from being an elegant mathematical discipline in its own right, graph theory can be applied in a wide range of areas (see the Preface). In a book of this size we cannot discuss a large number of these applications, and you should consult Berge [9], Chartrand and Oellermann [20], Deo [21], Roberts [25] and Tucker [26] for a wide range of practical problems, often with algorithms for their solution. In this section we outline four types of problem that involve paths and cycles: the shortest path problem, the critical path problem, the Chinese postman problem and the travelling salesman problem. The first two of these can be solved by efficient algorithms – finite step-by-step procedures that quickly yield the solutions. The third problem can also be solved by an efficient algorithm, but we consider only a special case here. For the fourth problem, no efficient algorithms are known; we must therefore choose between algorithms that take a long time to implement and heuristic algorithms that are quick to apply but give only an approximation to the solution. The shortest path problem Suppose that we have a diagram of the form shown in Fig. 2.35, in which the letters A-L refer to towns that are connected by roads. If the lengths of these roads are as marked, what is the length of a shortest path from A to L? (We write 'a shortest path' rather than 'the shortest path' since there may be more than one path with this shortest length.) Figure 2.35 Note that the numbers in the diagram might also refer, not to the length of each road, but to the time taken to travel along it, or to the cost of doing so. Thus, if we have an algorithm for solving this problem in its original formulation, then this algorithm can also be used to find a quickest or a cheapest route. Note also that we can easily obtain an upper bound for the answer by taking any path from A to L and calculating its length. For example, the path A2B2D2G2J2L has total length 18, and so the length of a shortest path cannot exceed 18.
2.4 Applications 53 In solving such problems, we regard our diagram as a connected graph in which a non-negative number is assigned to each edge. Such a graph is called a weighted graph, and the number assigned to each edge e is the weight of e, denoted by w(e). The problem is to find a path from A to L with minimum total weight. Note that, if we have a weighted graph in which each edge has weight 1, then the problem reduces to that of finding the number of edges in a shortest path from A to L. There are several methods that we can use to solve this problem. One way is to make a model of the map by knotting together pieces of string whose lengths are proportional to the lengths of the roads. To find a shortest path, take hold of the knots corresponding to A and L – and pull tight! However, there is a more mathematical way of solving it. The idea is to move across the map from left to right, labelling each vertex V with a number l(V ) that indicates the shortest distance from A to V. This means that, when we reach a vertex such as K in Fig. 2.35, then l(K) is labelled either l(H ) + 6 or l(I ) + 2, whichever is the smaller. Our aim is to find l(L). To apply the algorithm, we first assign A the label 0 and give B, E and C the temporary labels l(A) + 3, l(A) + 9 and l(A) + 2 – that is, 3, 9 and 2. We take the smallest of these, and write l(C ) = 2. C is now permanently labelled 2. We next look at the vertices adjacent to this labelled vertex C. We assign F the temporary label l(C) + 9 = 11, and we can lower the temporary label at E to l(C) + 6 = 8. The smallest temporary label is now 3 (at B), so we write l(B) = 3. B is now permanently labelled 3. Now we look at the vertices adjacent to B. We assign D the temporary label l(B) + 2 = 5, and we can lower the temporary label at E to l(B) + 4 = 7. The smallest temporary label is now 5 (at D), so we write l(D) = 5. D is now permanently labelled 5. Now we look at the vertices adjacent to D. The only one is G, and we assign it the temporary label l(D) + 3 = 8. The smallest temporary label is now 7 (at E), so we write l(E) = 7. E is now permanently labelled 7. Continuing in this way, we successively obtain the permanent labels l(G) = 8, l(H ) = 9, l(F) = 10, l(I ) = 12, l(J ) = 13, l(K ) = 14, l(L) = 17; these are shown on Fig. 2.36. It follows that the shortest path from A to L has length 17. Figure 2.36
54 Paths and cycles To find such a shortest path, we can restrict our attention to those edges whose length is the difference of the labels at its ends, such as KL and IK (since l(L) - l(K ) = 17 - 14 = 3 and l(K ) - l(I ) = 2). Using the labels to help us, we then trace back from L, via K and I, obtaining L 1 K 1 I 1 F 1 H 1 E 1 B 1 A. Thus the shortest path (which in this case is unique) from A to L is A 2 B 2 E 2 H 2 F 2 I 2 K 2 L. The critical path problem We now see how this algorithm can be adapted to yield the longest path in a digraph, and we illustrate its use in a 'critical path' problem relating to the scheduling of a series of operations. Suppose that we have a job to perform, such as the building of a house, and that this job can be divided into a number of activities, such as laying the foundations, putting on the roof, doing the wiring, etc. Some of these activities can be performed simultaneously, whereas some may need to be completed before others can be started. Can we find an efficient method for determining how to schedule the activities so that the entire job is completed in minimum time? In order to solve this problem, we construct a 'weighted digraph', or activity network, in which each arc represents the length of time taken for an activity. Such a network is given in Fig. 2.37. The vertex A represents the beginning of the job, and the vertex L represents its completion. Since the entire job cannot be completed until each path from A to L has been traversed, the problem reduces to that of finding the longest path from A to L. Figure 2.37 This is accomplished by using a technique known as programme evaluation and review technique (PERT), which is similar to the method we used to solve the shortest path problem above. This time, as we move across the digraph from left to right, we associate with each vertex V a label l(V) indicating the length of the longest path from A to V. As in the shortest path problem, we keep track of these labels by writing them next to the vertices they represent. However, unlike the problem that we considered above, there is no 'zigzagging', since all arcs are directed from left to right, so we can assign the permanent labels as we proceed. For example, for the digraph of Fig. 2.37, we assign:
2.4 Applications 55 to vertex A, the number 0; to vertex B, the number l(A) + 3 – that is, 3; to vertex C, the number l(A) + 2 – that is, 2; to vertex D, the number l(B) + 2 – that is, 5; to vertex E, the largest of the numbers l(A) + 9, l(B) + 4 and l(C) + 6 – that is, 9; to vertex F, the number l(C ) + 9 – that is, 11; to vertex G, the larger of the numbers l(D) + 3 and l(E) + 1 – that is, 10; to vertex H, the larger of the numbers l(E) + 2 and l(F) + 1 – that is, 12; to vertex I, the number l(F) + 2 – that is, 13; to vertex J, the larger of the numbers l(G) + 5 and l(H ) + 5 – that is, 17; to vertex K, the larger of the numbers l(H ) + 6 and l(I ) + 2 – that is, 18; to vertex L, the largest of the numbers l(H ) + 9, l(J ) + 5 and l(K ) + 33 – that is, 22. These labels are shown in Fig. 2.38. It follows that a longest path has length 22, and the job cannot therefore be completed until time 22. Figure 2.38 To find the longest path, we trace back from L, as we did for the shortest path problem. In this case, the unique longest path from A to L is A 2 C 2 F 2 H 2 J 2 L. It is often called a critical path, since any delay in an activity on this path creates a delay in the whole job. In scheduling a job, we therefore need to pay particular attention to the critical paths. We can also calculate the latest time by which any given operation must be completed if the work is not to be delayed. Working back from L, we see that we must reach K by time 22 - 3 = 19, J by time 22 - 5 = 17, H by time min{17 - 5, 22 - 9 and 19 - 6} = 12, and so on. The Chinese postman problem In this problem, discussed by the Chinese mathematician Meigu Guan, a postman wishes to deliver his letters, covering the least possible total distance and returning to
56 Paths and cycles his starting point. He must obviously traverse each road in his route at least once, but should avoid covering too many roads more than once. This problem can be reformulated in terms of a weighted graph, where the graph corresponds to the network of roads, and the weight of each edge is the length of the corresponding road. In this reformulation, the requirement is to find a closed walk of minimum total weight that includes each edge at least once. If the graph is Eulerian, then any Eulerian trail is a closed walk of the required type; such an Eulerian trail can be found by Fleury's algorithm (see Section 2.2). If the graph is not Eulerian, then the problem is much harder, although an efficient algorithm for its solution is known (see Gibbons [23]). To illustrate the ideas involved, we look at a special case, in which exactly two vertices have odd degree (see Fig. 2.39). Figure 2.39 Since vertices B and E are the only vertices of odd degree, we can find a semiEulerian trail from B to E covering each edge exactly once. In order to return to the starting point, covering the least possible distance, we now find the shortest path from E to B using the algorithm described above. The solution of the Chinese postman problem is then obtained by combining this shortest path E2F2A2B with the original semi-Eulerian trail, giving a total distance of 13 + 64 = 77. Note that, when we combine the shortest path and the semi-Eulerian trail, we get an Eulerian graph (see Fig. 2.40). Figure 2.40 The travelling salesman problem In this problem, a travelling salesman wishes to visit several given cities and return to his starting point, covering the least possible total distance. Such a route must be