3.1 Introduction to Graph Theory3.1.1 What is graph?
A graph G = (V, E) consists of a set of objects V = {v_{1}, v_{2}, …} called vertices, and another set E = {e_{1}, e_{2}, …} whose elements are called edges. Each edge e_{k} in E is identified with an unordered pair (v_{i}, v_{j}) of vertices. The vertices v_{i}, v_{j} associated with edge e_{k} are called the end vertices of e_{k}. The most common representation of graph is by means of a diagram, in which the vertices are represented as points and each edge as a line segment joining its end vertices. Often this diagram itself is referred to as a graph.

Fig 3-1.
In the Fig. 3-1 edge e_{1} having same vertex as both its end vertices is called a self-loop. There may be more than one edge associated with a given pair of vertices, for example e4 and e5 in Fig. 3-1. Such edges are referred to as parallel edges.
A graph that has neither self-loop nor parallel edges are called a simple graph, otherwise it is called general graph. It should also be noted that, in drawing a graph, it is immaterial whether the lines are drawn straight or curved, long or short: what is important is the incidence between the edges and vertices.
A graph is also called a linear complex, a 1-complex, or a one-dimensional complex. A vertex is also referred to as a node, a junction, a point, 0-cell, or an 0-simplex. Other terms used for an edge are a branch, a line, an element, a 1-cell, an arc, and a 1-simplex.
Because of its inherent simplicity, graph theory has a very wide range of applications in engineering, physical, social, and biological sciences, linguistics, and in numerous other areas. A graph can be used to represent almost any physical situation involving discrete objects and a relationship among them.
3.1.2 Finite and Infinite Graphs
Although in the definition of a graph neither the vertex set V nor the edge set E need be finite, in most of the theory and almost all applications these sets are finite. A graph with a finite number of vertices as well as a finite number of edges is called a finite graph; otherwise, it is an infinite graph.
3.1.3 Incidence and Degree
When a vertex v_{i} is an end vertex of some edge e_{j}, v_{i} and e_{j} are said to be incident with (on or to) each other. In Fig. 3-1, for example, edges e_{2}, e_{6}, and e_{7} are incident with vertex v_{4}. Two nonparallel edges are said to be adjacent if they are incident on a common vertex. For example, e_{2} and e_{7} in Fig. 3-1 are adjacent. Similarly, two vertices are said to be adjacent if they are the end vertices of the same edge. In Fig. 3-1, v_{4} and v_{5} are adjacent, but v_{1} and v_{4} are not.
The number of edges incident on a vertex v_{i}, with self-loops counted twice is called the degree, d(v_{i}), of vertex v_{i}. In Fig. 3-1, for example, d(v_{1}) = d(v_{3}) = d(v_{4}) = 3, d(v_{2}) = 4, and d(v_{5}) = 1. The degree of a vertex is sometimes also referred to as its valency. Since each edge contributes two degrees, the sum of the degrees of all vertices in G is twice the number of edges in G.
3.1.4 Isolated vertex, Pendent vertex, and Null graph
A vertex having no incident edge is called an isolated vertex. In other words, isolated vertices are vertices with zero degree. Vertex v_{4} and v_{7} in Fig. 3-2, for example, are isolated vertices. A vertex of degree one is called a pendent vertex or an end vertex. Vertex v_{3} in Fig. 3-2 is a pendant vertex. Two adjacent edges are said to be in series if their common vertex is of degree two. In Fig. 3-2, the two edges incident on v_{1} are in series.
Fig. 3-2 Graph containing isolated vertices, series edges and a pendant vertex.
In the definition of a graph G = (V, E), it is possible for the edge set E to be empty. Such a graph, without any edges, is called a null graph. In other words, every vertex in a null graph is an isolated vertex. A null graph of six vertices is shown in Fig. 3-3. Although the edge set E may be empty, the vertex set V must not be empty; otherwise, there is no graph. In other words, by definition, a graph must have at least one vertex.
Fig. 3-3 Null graph of six vertices.