Graph theory gives a pictorial representation of relation between a physical situation involving discrete objects. Wide range of applications can be seen in engineering, physical, social and  biological sciences. It is applied in designing circuits in electronic devices. Computer algorithm can be described by graphs. Theory of graphs is motivated first by the famous topologist Leonhard Euler in 1736 and later attracted most of the people due to its inherent simplicity and large applicability.
Study of graphs which are mathematical structures used to relationship between objects is known as graph theory. A graph is made up of vertices or nodes and lines also known as edges that connect them. A graph is formed by vertices and edges connecting the vertices. In graph theory, to decide the coloring of a graph we use chromatic numbers.

## Graph Theory Definitions

Definition of some terms which are directly related to the graph theory:

Isolated Vertex: A vertex whose degree is zero.

Pendant vertex: A vertex whose degree is one. An edge that has a pendant vertex as an end vertex is a pendant edge.

Trivial: A graph with only one vertex.

Simple graph: A graph is said ti be simple if it has no parallel edges or loops.

Null graph: A graph with no vertices.

Forest: A group of disconnected trees is called a forest.

Complete graph: A complete graph is a graph with N (Positive Integer) vertices and an edge between every two vertices.
There will be no loops and every two vertices share one edge only.

Planar graph:  A graph which is drawn in a plane without any cross edges. If there are cross edges it is redrawn to eliminate the crossings. They are widely used to represent maps.

Tree: A graph with no cycles is called a tree, and in a tree, there is only a single path between any two nodes. A tree on N vertices has exactly N - 1 edges.

Directed Graph: A directed graph which is generally denoted as G = (V, E) have a finite set V and a binary relation on V.

Undirected graph: An undirected graph denoted as G = (V, E) has a finite set V and a set of multi-sets of two elements from V.

Walk: A walk in the graph G = (V, E) is a  finite sequence of the form
v$_{i0}$, e$_{j1}$, v$_{i1}$,e$_{j2}$, .............., e$_{jk}$, v$_{ik}$ which consists of alternating vertices and edges of G.

Shortest Path Problem:  Shortest path problem is the problem of finding a path between two vertices in a graph such that the sum of the weights of its constituent edges is minimized.

Multi Graph : A graph which has multiple edges and no self loops is called a multi graph.

## Applications of Graph Theory

Graph theory is applied to various areas of mathematics, science and technology. Some of them are explained below:

Graph theory in Operation Research
Graph theory plays a significant role in operation research. In transport network, a graph is used
to model the transportation of commodity from one place to another. The objective is to maximize the flow or minimize the cost within the prescribed flow.

Graph theory in computer network security
The goal is to find a minimum vertex cover in the graph whose vertices are the routing servers and the edges are the connections between the routing servers. Then an optimal solution is found for worm propagation and a network defense strategy is defined.

Graph theory in finger print classification

For criminal investigation we use finger print classification. It uses databases for storing fingerprints. Relational graphs are more appropriate as each node is associated to a segmentation region. Error correcting graph matching is used and is based on classification rather than the structural methods.

## Graph Theory Examples

Example 1: Determine how many vertices are required to construct a graph with exactly 6 edges in which each vertex is of degree 2.
Solution: Let n be the number of vertices
We know that Sum of the degrees = Twice the number of edges
2 + 2 + 2 + 2 + ...................... n terms = 2(6)
2n = 12
n = 6
Therefore there  must be 6 vertices.

Example 2: Show that there exists no simple graph of 4 vertices, in which two vertices of degree 2, one vertex of degree  4 and one vertex of degree 6.
Solution: Let the number of edges of the required graph be m.
We know that Sum of the degrees = Twice the number of edges
2 + 2 + 4 + 6 =  2m
m = 7
However the number of edges does not exceed $\frac{n(n-1)}{2}$, where n is the number of vertices.
Here n = 4 and $\frac{n(n-1)}{2}$

= $\frac{4.3}{2}$

= 6

Thus the required graph does not exist as 7 > 6.