What is a Graph?
Definition − A graph (denoted as ) consists of a non-empty set of vertices or nodes V and a set of edges E.
Example − Let us consider, a Graph is where and

Degree of a Vertex − The degree of a vertex V of a graph G (denoted by deg (V)) is the number of edges incident with the vertex V.
| Vertex | Degree | Even / Odd |
|---|---|---|
| a | 2 | even |
| b | 2 | even |
| c | 3 | odd |
| d | 1 | odd |
Even and Odd Vertex − If the degree of a vertex is even, the vertex is called an even vertex and if the degree of a vertex is odd, the vertex is called an odd vertex.
Degree of a Graph − The degree of a graph is the largest vertex degree of that graph. For the above graph the degree of the graph is 3.
The Handshaking Lemma − In a graph, the sum of all the degrees of all the vertices is equal to twice the number of edges.
Types of Graphs
There are different types of graphs, which we will learn in the following section.
Null Graph
A null graph has no edges. The null graph of vertices is denoted by

Simple Graph
A graph is called simple graph/strict graph if the graph is undirected and does not contain any loops or multiple edges.

Multi-Graph
If in a graph multiple edges between the same set of vertices are allowed, it is called Multigraph. In other words, it is a graph having at least one loop or multiple edges.

Directed and Undirected Graph
A graph is called a directed graph if the edge set is made of ordered vertex pair and a graph is called undirected if the edge set is made of unordered vertex pair.


Connected and Disconnected Graph
A graph is connected if any two vertices of the graph are connected by a path; while a graph is disconnected if at least two vertices of the graph are not connected by a path. If a graph G is disconnected, then every maximal connected subgraph of is called a connected component of the graph .


Regular Graph
A graph is regular if all the vertices of the graph have the same degree. In a regular graph G of degree , the degree of each vertex of is r.

Complete Graph
A graph is called complete graph if every two vertices pair are joined by exactly one edge. The complete graph with n vertices is denoted by

Cycle Graph
If a graph consists of a single cycle, it is called cycle graph. The cycle graph with n vertices is denoted by

Bipartite Graph
If the vertex-set of a graph G can be split into two disjoint sets, and , in such a way that each edge in the graph joins a vertex in to a vertex in , and there are no edges in G that connect two vertices in or two vertices in , then the graph is called a bipartite graph.

Complete Bipartite Graph
A complete bipartite graph is a bipartite graph in which each vertex in the first set is joined to every single vertex in the second set. The complete bipartite graph is denoted by where the graph contains vertices in the first set and vertices in the second set.

Representation of Graphs
There are mainly two ways to represent a graph −
- Adjacency Matrix
- Adjacency List
Adjacency Matrix
An Adjacency Matrix is a 2D array of size where is the number of vertices in a undirected graph. If there is an edge between to then the value of and , otherwise the value will be zero. And for a directed graph, if there is an edge between to , then the value of , otherwise the value will be zero.
Adjacency Matrix of an Undirected Graph
Let us consider the following undirected graph and construct the adjacency matrix −

Adjacency matrix of the above undirected graph will be −
a | b | c | d | |
a | 0 | 1 | 1 | 0 |
b | 1 | 0 | 1 | 0 |
c | 1 | 1 | 0 | 1 |
d | 0 | 0 | 1 | 0 |
Adjacency Matrix of a Directed Graph
Let us consider the following directed graph and construct its adjacency matrix −

Adjacency matrix of the above directed graph will be −
a | b | c | d | |
a | 0 | 1 | 1 | 0 |
b | 0 | 0 | 1 | 0 |
c | 0 | 0 | 0 | 1 |
d | 0 | 0 | 0 | 0 |
Adjacency List
In adjacency list, an array of linked lists is used to represent the graph G with number of vertices. An entry represents the linked list of vertices adjacent to the vertex. The adjacency list of the undirected graph is as shown in the figure below −

Planar vs. Non-planar graph
Planar graph − A graph is called a planar graph if it can be drawn in a plane without any edges crossed. If we draw graph in the plane without edge crossing, it is called embedding the graph in the plane.

Non-planar graph − A graph is non-planar if it cannot be drawn in a plane without graph edges crossing.

Isomorphism
If two graphs G and H contain the same number of vertices connected in the same way, they are called isomorphic graphs (denoted by ).
It is easier to check non-isomorphism than isomorphism. If any of these following conditions occurs, then two graphs are non-isomorphic −
- The number of connected components are different
- Vertex-set cardinalities are different
- Edge-set cardinalities are different
- Degree sequences are different
Example
The following graphs are isomorphic −

Homomorphism
A homomorphism from a graph to a graph is a mapping (May not be a bijective mapping) such that − . It maps adjacent vertices of graph to the adjacent vertices of the graph .
Properties of Homomorphisms
A homomorphism is an isomorphism if it is a bijective mapping.
Homomorphism always preserves edges and connectedness of a graph.
The compositions of homomorphisms are also homomorphisms.
To find out if there exists any homomorphic graph of another graph is a NPcomplete problem.
Euler Graphs
A connected graph is called an Euler graph, if there is a closed trail which includes every edge of the graph . An Euler path is a path that uses every edge of a graph exactly once. An Euler path starts and ends at different vertices.
An Euler circuit is a circuit that uses every edge of a graph exactly once. An Euler circuit always starts and ends at the same vertex. A connected graph is an Euler graph if and only if all vertices of are of even degree, and a connected graph is Eulerian if and only if its edge set can be decomposed into cycles.

The above graph is an Euler graph as covers all the edges of the graph.

Hamiltonian Graphs
A connected graph is called Hamiltonian graph if there is a cycle which includes every vertex of and the cycle is called Hamiltonian cycle. Hamiltonian walk in graph is a walk that passes through each vertex exactly once.
If is a simple graph with n vertices, where If for each vertex , then the graph is Hamiltonian graph. This is called Dirac's Theorem.
If is a simple graph with vertices, where if for each pair of non-adjacent vertices x and y, then the graph is Hamiltonian graph. This is called Ore's theorem.


Graph Coloring
Graph coloring is the procedure of assignment of colors to each vertex of a graph G such that no adjacent vertices get same color. The objective is to minimize the number of colors while coloring a graph. The smallest number of colors required to color a graph G is called its chromatic number of that graph. Graph coloring problem is a NP Complete problem.
Method to Color a Graph
The steps required to color a graph G with n number of vertices are as follows −
Step 1 − Arrange the vertices of the graph in some order.
Step 2 − Choose the first vertex and color it with the first color.
Step 3 − Choose the next vertex and color it with the lowest numbered color that has not been colored on any vertices adjacent to it. If all the adjacent vertices are colored with this color, assign a new color to it. Repeat this step until all the vertices are colored.
Example

In the above figure, at first vertex is colored red. As the adjacent vertices of vertex a are again adjacent, vertex and vertex are colored with different color, green and blue respectively. Then vertex is colored as red as no adjacent vertex of is colored red. Hence, we could color the graph by 3 colors. Hence, the chromatic number of the graph is 3.
Applications of Graph Coloring
Some applications of graph coloring include −
- Register Allocation
- Map Coloring
- Bipartite Graph Checking
- Mobile Radio Frequency Assignment
- Making time table, etc.
Graph Traversal
Graph traversal is the problem of visiting all the vertices of a graph in some systematic order. There are mainly two ways to traverse a graph.
- Breadth First Search
- Depth First Search
Breadth First Search
Breadth First Search (BFS) starts at starting level-0 vertex of the graph . Then we visit all the vertices that are the neighbors of . After visiting, we mark the vertices as "visited," and place them into level-1. Then we start from the level-1 vertices and apply the same method on every level-1 vertex and so on. The BFS traversal terminates when every vertex of the graph has been visited.
BFS Algorithm
The concept is to visit all the neighbor vertices before visiting other neighbor vertices of neighbor vertices.
Initialize status of all nodes as “Ready”.
Put source vertex in a queue and change its status to “Waiting”.
Repeat the following two steps until queue is empty −
Remove the first vertex from the queue and mark it as “Visited”.
Add to the rear of queue all neighbors of the removed vertex whose status is “Ready”. Mark their status as “Waiting”.
Problem
Let us take a graph (Source vertex is ‘a’) and apply the BFS algorithm to find out the traversal order.

Solution −
Initialize status of all vertices to “Ready”.
Put a in queue and change its status to “Waiting”.
Remove a from queue, mark it as “Visited”.
Add a’s neighbors in “Ready” state b, d and e to end of queue and mark them as “Waiting”.
Remove b from queue, mark it as “Visited”, put its “Ready” neighbor c at end of queue and mark c as “Waiting”.
Remove d from queue and mark it as “Visited”. It has no neighbor in “Ready” state.
Remove e from queue and mark it as “Visited”. It has no neighbor in “Ready” state.
Remove c from queue and mark it as “Visited”. It has no neighbor in “Ready” state.
Queue is empty so stop.
So the traversal order is −
The alternate orders of traversal are −
Or,
Or,
Or,
Or,
Application of BFS
- Finding the shortest path
- Minimum spanning tree for un-weighted graph
- GPS navigation system
- Detecting cycles in an undirected graph
- Finding all nodes within one connected component
Complexity Analysis
Let be a graph with number of vertices and number of edges. If breadth first search algorithm visits every vertex in the graph and checks every edge, then its time complexity would be −
It may vary between and
Depth First Search
Depth First Search (DFS) algorithm starts from a vertex , then it traverses to its adjacent vertex (say x) that has not been visited before and mark as "visited" and goes on with the adjacent vertex of and so on.
If at any vertex, it encounters that all the adjacent vertices are visited, then it backtracks until it finds the first vertex having an adjacent vertex that has not been traversed before. Then, it traverses that vertex, continues with its adjacent vertices until it traverses all visited vertices and has to backtrack again. In this way, it will traverse all the vertices reachable from the initial vertex .
DFS Algorithm
The concept is to visit all the neighbor vertices of a neighbor vertex before visiting the other neighbor vertices.
Initialize status of all nodes as “Ready”
Put source vertex in a stack and change its status to “Waiting”
Repeat the following two steps until stack is empty −
Pop the top vertex from the stack and mark it as “Visited”
Push onto the top of the stack all neighbors of the removed vertex whose status is “Ready”. Mark their status as “Waiting”.
Problem
Let us take a graph (Source vertex is ‘a’) and apply the DFS algorithm to find out the traversal order.

Solution
Initialize status of all vertices to “Ready”.
Push a in stack and change its status to “Waiting”.
Pop a and mark it as “Visited”.
Push a’s neighbors in “Ready” state e, d and b to top of stack and mark them as “Waiting”.
Pop b from stack, mark it as “Visited”, push its “Ready” neighbor c onto stack.
Pop c from stack and mark it as “Visited”. It has no “Ready” neighbor.
Pop d from stack and mark it as “Visited”. It has no “Ready” neighbor.
Pop e from stack and mark it as “Visited”. It has no “Ready” neighbor.
Stack is empty. So stop.
So the traversal order is −
The alternate orders of traversal are −
Or,
Or,
Or,
Or,
Complexity Analysis
Let be a graph with number of vertices and number of edges. If DFS algorithm visits every vertex in the graph and checks every edge, then the time complexity is −
Applications
- Detecting cycle in a graph
- To find topological sorting
- To test if a graph is bipartite
- Finding connected components
- Finding the bridges of a graph
- Finding bi-connectivity in graphs
- Solving the Knight’s Tour problem