Chapter-1 INTRODUCTION TO GRAPH THEORY

A graph G = (V, E) is a set of objects, V = {v1, v2, . . .} called vertices, and a set E = {e1, e2, . . .} called edges, such that an edge ek is determined with an unordered pair (vi, vj) of vertices. The vertices vi, vj that belong to an edge ek are called the end vertices of ek. A graph is generally represented by a diagram, with points representing vertices and line segments joining these vertices representing edges. This diagram is generally referred to as a graph. For example, the figure below depicts a graph. [1]

Figure 1: A graph with 5 vertices and 10 edges

According to the definition above, an edge is associated with a vertex pair (vi,vi). A self loop is an edge that has the same initial and final vertices. Edge e1 in the above figure is a self-loop. Hence, a given pair of vertices may have more than one edge, for example, edges e4 and e5. These edges are termed parallel edges. A simple graph is a graph that does not have any self loops or parallel edges. There are many applications of graph theory in various fields. In engineering, in physical, social, and biological sciences, in linguistics, and in numerous other areas graph theory helps to solve many problems. Any physical involving discrete objects and their relationships can be shown by using graphs. The concept of Graph theory began in 1736 when Euler considered the Konigsberg bridge problem. [1]

1.1 Konigsberg Bridge Problem:
One of the classic and well known examples in graph theory is the Konigsberg Bridge Problem. The first solution to this problem was given by Leonard Euler in 1736, by using a graph. The first paper ever on graphs and their properties was written by him and thus he became the originator of graph theory. The Konigsberg bridge problem is as follows. The Pregel river in Konigsberg surrounds two islands say, A and C. These