GRAPH THEORY – MATHEMATICS : PAPER II (2) – MTC 122 – Golden Series

1. An Introduction to Graph

1.1 Graph Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

1.1.1 Basic Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1.2 Degree of a vertex . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.2 Graph Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3 Types of a Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.4 Types of Digraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.5 Representing Graphs and Graph Isomorphism . . . . . . . . . . . . . . . . . . . . . . 19

1.5.1 Representation of Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.5.2 Isomorphism of Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

1.6 Operations on Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

1.6.1 Subgraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
1.6.2 Deletion of vertices and edges from a Graph . . . . . . . . . . . . . . . . . . . 34
1.6.3 Complement of a Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
1.6.4 Union, Intersection, Ring sum and Product of Graphs . . . . . . . . . . . . . . 37

2. Connected graphs

2.1 Walk, Path and Circuits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
2.2 Connected Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
2.3 Counting paths between vertices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
2.4 Isthmus and Cut vertex . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

2.4.1 Connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

2.5 A Shortest-Path algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

3. Euler and Hamilton Path

3.1 Euler Path and Euler circuit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75

3.1.1 Fleury’s algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78

3.2 Hamilton Path and Circuit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
3.3 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88

4 Trees

4.1 Definition and Properties of a tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
4.2 Centre of a tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
4.3 Spanning trees: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98

4.3.1 Shortest spanning tree, Kruskal’s and Prims algorithm . . . . . . . . . . . . . 102

4.4 Binary tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
4.5 m-ary trees: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
4.6 Tree Traversal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117

4.6.1 Infix, Prefix and Postfix notation . . . . . . . . . . . . . . . . . . . . . . . . . 123

About the Book :

This book is based on a course Graph theory. We write this book as per the revised syllabus
of F.Y. B.Sc.(Computer Science) Mathematics, revised by Savitribai Phule Pune University, Pune,
implemented from June 2019. Graph theory is the most useful subject in all branches of mathematics
and it is used extensively in applied mathematics and engineering.
Graphs theory is the study of graphs, which are mathematical structures used to model pairwise
relations between objects. It is a bridge connecting mathematics with various branches of computer
science. We study how problems in almost every conceivable discipline can be solved using graph
models.
The aim of this textbook on Graph theory is to introduce basic concept in graph theory and some
shortest path algorithm to model computation-related problems..
In chapter 1, basic concepts and terms of graph theory have been introduced. We will also introduce
several important families of graphs often used as examples and in models. We will show how to
represent graphs in several different ways and a one-to-one correspondence between their vertex sets
that preserves edges.
In the second chapter, we discuss concepts like walk, path, cycle etc. which would help us to
understand the definition of connected graph. We also study isthmus and cut vertex and algorithm
to find shortest path between two vertices.
The aim of third chapter is to equip students with the Euler and Hamilton circuits. The chapter
concludes with their application to Travelling salesman and Chinese Postman problem.
In fourth chapter, we will focus on a particular type of graph called a tree, so named because such
graphs resemble trees. Trees are used as models in such diverse areas as computer science, chemistry,
geology, botany, and psychology. We will describe a variety of such models based on trees.