Basic Graph Theory (Undergraduate Topics in Computer Science)

Undergraduate Topics in Computer Science

Md. Saidur Rahman

Basic

Graph

Theory

Undergraduate Topics in Computer Science

Series editor

Ian Mackie

Advisory Board

Samson Abramsky, University of Oxford, Oxford, UK

Karin Breitman, Pontifical Catholic University of Rio de Janeiro, Rio de Janeiro, Brazil

Chris Hankin, Imperial College London, London, UK

Dexter C. Kozen, Cornell University, Ithaca, USA

Andrew Pitts, University of Cambridge, Cambridge, UK

Hanne Riis Nielson, Technical University of Denmark, Kongens Lyngby, Denmark

Steven S. Skiena, Stony Brook University, Stony Brook, USA

Iain Stewart, University of Durham, Durham, UK

Undergraduate Topics in Computer Science (UTiCS) delivers high-quality instructional

content for undergraduates studying in all areas of computing and information science.

From core foundational and theoretical material to final-year topics and applications, UTiCS

books take a fresh, concise, and modern approach and are ideal for self-study or for a one- or

two-semester course. The texts are all authored by established experts in their fields,

reviewed by an international advisory board, and contain numerous examples and problems.

Many include fully worked solutions.

More information about this series at http://www.springer.com/series/7592

Md. Saidur Rahman

Basic Graph Theory

123

Md. Saidur Rahman

Department of Computer Science and Engineering

Bangladesh University of Engineering and Technology (BUET)

Dhaka

Bangladesh

ISSN 1863-7310 ISSN 2197-1781 (electronic)

Undergraduate Topics in Computer Science

ISBN 978-3-319-49474-6 ISBN 978-3-319-49475-3 (eBook)

DOI 10.1007/978-3-319-49475-3

Library of Congress Control Number: 2016961329

© Springer International Publishing AG 2017

This work is subject to copyright. All rights are reserved by the Publisher, whether the whole or part

of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations,

recitation, broadcasting, reproduction on microfilms or in any other physical way, and transmission

or information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar

methodology now known or hereafter developed.

The use of general descriptive names, registered names, trademarks, service marks, etc. in this

publication does not imply, even in the absence of a specific statement, that such names are exempt from

the relevant protective laws and regulations and therefore free for general use.

The publisher, the authors and the editors are safe to assume that the advice and information in this

book are believed to be true and accurate at the date of publication. Neither the publisher nor the

authors or the editors give a warranty, express or implied, with respect to the material contained herein or

for any errors or omissions that may have been made. The publisher remains neutral with regard to

jurisdictional claims in published maps and institutional affiliations.

Printed on acid-free paper

This Springer imprint is published by Springer Nature

The registered company is Springer International Publishing AG

The registered company address is: Gewerbestrasse 11, 6330 Cham, Switzerland

Preface

This book is written based on my class notes developed while teaching the

undergraduate graph theory course “Basic Graph Theory” at the Department of

Computer Science and Engineering, Bangladesh University of Engineering and

Technology (BUET). Due to numerous applications in modeling problems in

almost every branch of science and technology, graph theory has appeared as a vital

component of mathematics and computer science curricula of universities all over

the world.

There are several excellent books on graph theory. Harary’s book (Graph

Theory, Addison-Wesley, Reading, Mass, 1969) is legendary while Wilson’s book

(Introduction to Graph Theory, 4th edn, Longman, 1996) is an excellent intro￾ductory textbook of graph theory. The book by West (Introduction to Graph

Theory, 2nd edn, Prentice-Hall, 2001) is the most comprehensive book, which

covers both introductory and advanced topics of graph theory. Agnarsson and

Greenlaw in their book (Graph Theory: Modeling, Applications and Algorithms,

Pearson Education, Inc., 2007) presented graph theory in a rigorous way using

practical, intuitive, and algorithmic approaches. This list also includes many other

nice books such as the book of Deo (Graph Theory with Applications to

Engineering and Computer Science, 1974) and the book of Pirzada (An

Introduction to Graph Theory, University Press, India, 2009). Since I have followed

those books in my classes, most of the contents of this book are taken from those

books. However, in this book all good features of those books are tied together with

the following features:

• terminologies are presented in simple language with illustrative examples,

• proofs are presented with every details and illustrations for easy understanding,

• constructive proofs are preferred to existential proofs so that students can easily

develop algorithms.

This book is primarily intended for use as a textbook at the undergraduate level.

Topics are organized sequentially in such a way that an instructor can follow as it is.

The organization of the book is as follows. In Chapter 1 historical background,

motivation, and applications of graph theory are presented. Chapter 2 provides

v

basic graph theoretic terminologies. Chapter 3 deals with paths, cycles, and con￾nectivity. Eulerian graphs and Hamiltonian cycles are also presented in this chapter.

Chapter 4 deals with trees whereas Chapter 5 focuses on matchings and coverings.

Planar graphs are treated in Chapter 6. Basic and fundamental results on graph

coloring are presented in Chapter 7. Chapter 8 deals with digraphs. Chapters 9 and

10 exhibit the unique feature of this book; Chapter 9 presents some special classes

of graphs, and some research topics are introduced in Chapter 10. While teaching

the graph theory course to undergraduate students of computer science and engi￾neering, I have found many students who started their research career by doing

research on graph theory and graph algorithms. Some special classes of graphs (on

which many hard graph problems are efficiently solvable) together with some

research topics can give direction to such students for selecting their first research

topics.

While revising research articles of my students I often face difficulties, since they

are not familiar with formal mathematical writing. Thus I have used formal

mathematical styles in writing this book so that the students can learn these styles

while reading this book.

I would like to thank my undergraduate students of the Department of Computer

Science and Engineering, BUET, who took notes on my class lectures and handed

those to me. My undergraduate student Muhammad Jawaherul Alam started to

compile those lectures. I continued it and prepared a complete manuscript during

my sabbatical leave at Military Institute of Science and Technology (MIST), Dhaka.

I have used the manuscript in undergraduate courses at BUET and MIST for

students’ feedback. I thank the students of Basic Graph Theory Course at BUET

and MIST for pointing out several typos and inconsistencies. My heartfelt thanks go

to Shin-ichi Nakano of Gunma University who read the manuscript thoroughly,

pointed out several mistakes and suggested for improving the presentation of the

book. I must appreciate the useful feedback provided by my former Ph.D. student

Md. Rezaul Karim who used the manuscript in a course in Computer Science and

Engineering Department of University of Dhaka. Some parts of this book are taken

from our joint papers listed in bibliography; I thank all coauthors of those joint

papers. I would like to thank my students Afia, Aftab, Debajyoti, Iqbal, Jawaherul,

Manzurul, Moon, Rahnuma, Rubaiyat, and Shaheena for their useful feedback.

I would particularly like to express my gratitude to Mohammad Kaykobad for his

continuous encouragement. I thank Md. Afzal Hossain of MIST for providing me a

wonderful environment in MIST for completing this book. I sincerely appreciate the

editorial team of Springer for their nice work.

I am very much indebted to my Ph.D. supervisor Takao Nishizeki for his

enormous contribution in developing my academic and research career. I thank my

parents for their blessings and good wishes. Of course, no word can express the

support given by my family; my wife Anisa, son Atiq, and daughter Shuprova.

Dhaka, Bangladesh Md. Saidur Rahman

2017

vi Preface

Contents

1 Graphs and Their Applications ............................. 1

1.1 Introduction ........................................ 1

1.2 Applications of Graphs................................ 2

1.2.1 Map Coloring ................................ 2

1.2.2 Frequency Assignment ......................... 3

1.2.3 Supply Gas to a Locality........................ 4

1.2.4 Floorplanning ................................ 6

1.2.5 Web Communities............................. 7

1.2.6 Bioinformatics................................ 7

1.2.7 Software Engineering .......................... 8

Exercises................................................ 8

References............................................... 9

2 Basic Graph Terminologies ................................ 11

2.1 Graphs and Multigraphs ............................... 11

2.2 Adjacency, Incidence, and Degree ....................... 13

2.2.1 Maximum and Minimum Degree.................. 13

2.2.2 Regular Graphs ............................... 14

2.3 Subgraphs.......................................... 15

2.4 Some Important Trivial Classes of Graphs ................. 16

2.4.1 Null Graphs.................................. 17

2.4.2 Complete Graphs.............................. 17

2.4.3 Independent Set and Bipartite Graphs .............. 17

2.4.4 Path Graphs.................................. 18

2.4.5 Cycle Graphs................................. 19

2.4.6 Wheel Graphs ................................ 19

2.5 Operations on Graphs................................. 19

2.5.1 Union and Intersection of Graphs ................. 19

2.5.2 Complement of a Graph ........................ 20

2.5.3 Subdivisions ................................. 21

vii

2.5.4 Contraction of an Edge ......................... 22

2.6 Graph Isomorphism .................................. 22

2.7 Degree Sequence .................................... 24

2.8 Data Structures and Graph Representation ................. 26

2.8.1 Adjacency Matrix ............................. 26

2.8.2 Incidence Matrix .............................. 27

2.8.3 Adjacency List ............................... 28

Exercises................................................ 28

References............................................... 29

3 Paths, Cycles, and Connectivity ............................. 31

3.1 Walks, Trails, Paths, and Cycles......................... 31

3.2 Eulerian Graphs ..................................... 34

3.3 Hamiltonian Graphs .................................. 36

3.4 Connectivity ........................................ 39

3.4.1 Connected Separable Graphs..................... 41

3.4.2 Block-Cutvertex Tree .......................... 42

3.4.3 2-Connected Graphs ........................... 43

3.4.4 Ear Decomposition ............................ 44

Exercises................................................ 46

References............................................... 46

4 Trees .................................................. 47

4.1 Introduction ........................................ 47

4.2 Properties of a Tree .................................. 47

4.3 Rooted Trees ....................................... 50

4.4 Spanning Trees of a Graph............................. 51

4.5 Counting of Trees.................................... 54

4.6 Distances in Trees and Graphs .......................... 58

4.7 Graceful Labeling .................................... 59

Exercises................................................ 60

References............................................... 62

5 Matching and Covering ................................... 63

5.1 Matching .......................................... 63

5.1.1 Perfect Matching .............................. 63

5.1.2 Maximum Matching ........................... 63

5.1.3 Hall’s Matching Condition ...................... 66

5.2 Independent Set ..................................... 68

5.3 Covers ............................................ 68

5.4 Dominating Set...................................... 69

5.5 Factor of a Graph .................................... 72

Exercises................................................ 73

References............................................... 74

viii Contents

6 Planar Graphs........................................... 77

6.1 Introduction ........................................ 77

6.2 Characterization of Planar Graphs........................ 77

6.3 Plane Graphs ....................................... 78

6.3.1 Euler’s Formula............................... 82

6.3.2 Dual Graph .................................. 84

6.4 Thickness of Graphs.................................. 85

6.5 Straight-Line Drawings of Planar Graphs .................. 85

Exercises................................................ 87

References............................................... 89

7 Graph Coloring .......................................... 91

7.1 Introduction ........................................ 91

7.2 Vertex Coloring ..................................... 91

7.3 Edge Coloring ...................................... 94

7.4 Face Coloring (Map Coloring) .......................... 97

7.5 Chromatic Polynomials................................ 97

7.6 Acyclic Coloring..................................... 98

Exercises................................................ 101

References............................................... 102

8 Digraphs................................................ 103

8.1 Introduction ........................................ 103

8.2 Digraph Terminologies ................................ 103

8.3 Eulerian Digraphs.................................... 105

8.4 Hamiltonian Digraphs................................. 106

8.5 Digraphs and Tournaments............................. 106

8.6 Flow Networks ...................................... 107

Exercises................................................ 109

References............................................... 109

9 Special Classes of Graphs.................................. 111

9.1 Introduction ........................................ 111

9.2 Outerplanar Graphs................................... 111

9.3 Triangulated Plane Graphs ............................. 114

9.3.1 Canonical Ordering ............................ 114

9.3.2 Separating Triangles ........................... 116

9.3.3 Plane 3-Trees................................. 119

9.4 Chordal Graphs...................................... 121

9.5 Interval Graphs...................................... 124

9.6 Series-Parallel Graphs................................. 125

9.7 Treewidth and Pathwidth .............................. 130

Exercises................................................ 131

References............................................... 132

Contents ix

10 Some Research Topics .................................... 135

10.1 Introduction ........................................ 135

10.2 Graph Representation ................................. 135

10.3 Graph Drawing ...................................... 137

10.3.1 Drawings of Planar Graphs ...................... 138

10.3.2 Simultaneous Embedding ....................... 145

10.3.3 Drawings of Nonplanar Graphs................... 146

10.4 Graph Labeling...................................... 148

10.5 Graph Partitioning ................................... 150

10.6 Graphs in Bioinformatics .............................. 152

10.6.1 Hamiltonian Path for DNA Sequencing............. 152

10.6.2 Cliques for Protein Structure Analysis.............. 153

10.6.3 Pairwise Compitability Graphs ................... 154

10.7 Graphs in Wireless Sensor Networks ..................... 156

10.7.1 Topology Control ............................. 157

10.7.2 Fault Tolerance ............................... 158

10.7.3 Clustering ................................... 158

References............................................... 159

Index ...................................................... 165

x Contents

Chapter 1

Graphs and Their Applications

1.1 Introduction

A graph consists of a set of vertices and set of edges, each joining two vertices.

Usually an object is represented by a vertex and a relationship between two objects

is represented by an edge. Thus a graph may be used to represent any information

that can be modeled as objects and relationships between those objects. Graph theory

deals with study of graphs. The foundation stone of graph theory was laid by Euler in

1736 by solving a puzzle called Königsberg seven-bridge problem [1]. Königsberg

is an old city in Eastern Prussia lies on the Pregel River. The Pregel River surrounds

an island called Kneiphof and separates into two branches as shown in Fig. 1.1(a)

where four land areas are created: the island a, two river banks b and c, and the land

d between two branches. Seven bridges connect the four land areas of the city. It is

said that the people of Königsberg used to entertain themselves by trying to devise

a walk around the city which would cross each of the seven bridges just once. Since

their attempts had always failed, many of them believed that the task was impossible,

but there was no proof until 1736. In that year, one of the leading mathematicians

of that time, Leonhard Euler published a solution to the problem that no such walk

is possible. He not only dealt with this particular problem, but also gave a general

method for other problems of the same type. Euler constructed a mathematical model

for the problem in which each of the four lands a, b, c and d is represented by a point

and each of the seven bridges is represented by a curve or a line segment as illustrated

in Fig. 1.2(b). The problem can now be stated as follows: Beginning at one of the

points a, b, c and d, is it possible to trace the figure without traversing the same edge

twice? The mathematical model constructed for the problem is known as a graph

model of the problem. The points a, b, c and d are called vertices, the line segments

are called edges, and the whole diagram is called a graph.

Before presenting some applications of graphs, we need to know some

terminologies. A graph G is a tuple (V, E) which consists of a finite set V of

vertices and a finite set E of edges; each edge is an unordered pair of vertices. The

two vertices associated with an edge e are called the end-vertices of e. We often

© Springer International Publishing AG 2017

M.S. Rahman, Basic Graph Theory, Undergraduate Topics in Computer Science,

DOI 10.1007/978-3-319-49475-3_1

1

2 1 Graphs and Their Applications

(b)

c

b

d

a

a d

(a)

b

c

Fig. 1.1 The graph model for Königsberg bridges

denote by (u, v), an edge between two vertices u and v. We also denote the set of

vertices of a graph G by V(G) and the set of edges of G by E(G). Let e = (u, v)

be an edge of a graph G. Then the two vertices u and v are said to be adjacent in

G and the edge e is said to be incident to the vertices u and v. The vertex u is also

called a neighbor of v in G and vice versa. The graph in Fig. 1.2(b) has six vertices

a, b, c, d, e and f , and ten edges. Vertices a and b are the end vertices of edge (a, b).

So a and b are adjacent. Vertices b, c and f are the neighbors of the vertex a.

1.2 Applications of Graphs

Graphs have applications in almost all branches of science and engineering [2, 3]. In

this section we will see applications of graphs in modeling some real-world problems.

1.2.1 Map Coloring

Given a map containing several countries, where each country is a contiguous region

in the map, we are asked to color the countries using different colors so that no two

countries with a common boundary share the same color. Of course, our objective is to

use a minimum number of colors. Such a problem can easily be modeled by a graph as

follows. We represent each country by a vertex and add an edge between two vertices

1.2 Applications of Graphs 3

(a) (b)

a

f

e

b

d

a

f

e

d

b

c

c

1

2

4

2

3

1

Fig. 1.2 (a) A map and (b) a graph model for map coloring

if the two countries corresponding to the vertices share a boundary, as illustrated in

Fig. 1.2 where Fig. 1.2(b) illustrates the graph model for the map in Fig. 1.2(a). Now

the problem becomes a graph problem which asks to color the vertices of the graph

using a minimum number of colors so that two adjacent vertices get different colors.

The vertices of the graph in Fig. 1.2(b) are colored with four colors and hence the

regions of the map in Fig. 1.2(a) can be colored with four colors. Interestingly, the

regions of every map can be colored with four colors [4].

1.2.2 Frequency Assignment

A communication engineer is going to assign frequencies to several transmitters.

Due to the physical locations of the transmitters, some of the transmitter pairs are in

the range of interference. Assume that there are n transmitters and that n frequencies

{1, 2,..., n} will be assigned to the transmitters such that no two transmitters are

assigned the same frequency, and if two transmitters are in interference range then

the difference between their assigned frequencies should be as large as possible. We

can easily develop a graph model of this problem as follows. We construct a graph

G by representing each transmitter by a vertex of G and add an edge between two

vertices u and v of G if the transmitters corresponding to vertices u and v are in

interference range. Now the frequency assignment problem becomes the problem of

labeling the vertices of G by 1, 2,..., n such that one label is used for exactly one

vertex by keeping the difference of the labels of two end vertices of an edge is as large

as possible [5]. Five transmitters a, b, c, d, e with their transmission ranges indicated

by circles are shown in Fig. 1.3(a) and the graph model is shown in Fig. 1.3(b). In

the graph model, there is an edge between a and b since their transmission ranges

overlap, i.e., they are in the range of interference. Other edges have also been added

in the graph following the same rule. Observe that the frequencies are assigned to

the vertices in such a way that the minimum difference between two adjacent labels

is 2.

4 1 Graphs and Their Applications

4 13 52

(b)

(a)

3 23 2

a

b

c

e

d

a b c d e

Fig. 1.3 (a) Transmitters with their transmission ranges, (b) a graph model with frequency

assignment

1.2.3 Supply Gas to a Locality

A gas company wants to supply gas to a locality from a single gas source. They are

allowed to pass the underground gas lines along the road network only, because no

one allows to pass gas lines through the bottom of one’s building. The road network

divides the locality into many regions as illustrated in Fig. 1.4(a), where each road

is represented by a line segment and a point at which two or more roads meet is

represented by a small black circle. A point at which two or more roads meet is

called an intersection point. Each region is bounded by some line segments and

intersection points. These regions need to be supplied gas. If a gas line reaches an

intersection point on the boundary of a region, then the region may receive gas from

the line at that intersection point. Thus, the gas lines should reach the boundaries of

all the regions of the locality. Gas will be supplied from a gas field which is located

outside of the locality, and a single pipe line will be used to supply gas from the gas

field to an intersection point on the outer boundary of the locality.

The gas company wants to minimize the establishment cost of gas lines by select￾ing the roads for laying gas lines such that the total length of the selected roads

is minimal. Since gas will be supplied from the gas field using a single line to the

locality, the selected road network should be connected and contain an intersection

point on the outer boundary of the locality. Thus, the gas company needs to find a

set of roads that induces a connected road network, supply gas in all the regions of

the locality and the length of the induced road network is minimum. Such a set of

roads is illustrated by thick lines in Fig. 1.4(b).