Graph Theory and

Algorithms
Applications of Graph Theory in CS
The major applications of Graph Theory in Computer Science are:
• Computer Networks – Graphs help in finding the shortest and most
efficient path for data transfer between computers.
• Social Networks – People are nodes, and connections are edges. Graphs
are used for friend suggestions and finding influencers.
• Operating Systems – Resource Allocation Graphs detect deadlocks by
checking for cycles.
• Compiler Design – Control Flow Graphs show program execution flow, and
graph coloring is used for register allocation.
• Search Engines (Web Graphs) – The internet is a huge directed graph of
web pages. PageRank uses graph theory to rank search results.
Introduction
• A graph is a mathematical structure used to represent a set of objects
and the connections between them:
• The objects are called vertices ( or nodes),
• The connections between them are called edges (or links).

• Formally: A graph G is defined as: G - (V, E), Where:

V = a set of vertices (or nodes), representing objects.
E = a set of edges (or links), representing connections between pairs of vertices.
Basic Concepts
• Vertex (Node): A fundamental element of a graph, representing an object, entity, or point.
• Edge (Link): A connection between two vertices, showing a relationship or pathway.
• Adjacent Vertices: Two vertices that are directly connected by an edge.
• Degree of a Vertex: The number of edges incident on a vertex.
• In a directed graph, we distinguish between in-degree (incoming edges) and out-
degree (outgoing edges).
• Path: A sequence of vertices connected by edges, with no vertex repeated.
• Cycle: A path that begins and ends at the same vertex, forming a closed loop.
• Connected Graph: A graph in which there exists a path between every pair of vertices.
• Subgraph: A smaller graph formed using a subset of the vertices and edges of a larger
graph.
• Loop: An edge that connects a vertex back to itself.
• Parallel Edges: Two or more edges that connect the same pair of vertices.
• Vertex (Node):
Example: 1, 2, 3, 4, 5, 6 are vertices.
• Edge (Link):
Example: The line between vertex 3 and 5 is an edge.
• Adjacent Vertices:
Example: 3 and 5 are adjacent because they share an edge.
• Degree of a Vertex:
Example: Vertex 3 has degree 3 (connected to 1, 4, and 5).
• Path:
Example: One path is 5 → 3 → 1 → 2 → 6.
• Cycle:
Example: 1 → 3 → 4 → 2 → 1 forms a cycle.
• Connected Graph
Example: From vertex 5, we can reach vertex 6 via
5 → 3 → 2 → 6, so this graph is connected.
Types of Graph:

• Isolated Vertex: A vertex of graph which is not adjacent to any other

vertex (which is not connected by an edge to any other vertex) is
called an isolated vertex.
• Example : Here 𝒗𝟒 is an isolated vertex.
• Null Graph: A graph containing only isolated vertex (no edges) is
called a null graph.

• Directed Graph or Digraph: If in graph 𝑮 = 𝑽 , 𝑬 each edge 𝒆 ∈ 𝑬 is

associated with an ordered pair of vertices, then 𝑮 is called a directed
graph or digraph.
• Undirected Graph: If in graph 𝑮 = 𝑽 , 𝑬 each edge 𝒆 ∈ 𝑬 is associated
with an unordered pair of vertices, then 𝑮 is called an undirected graph.

• Self Loop: An edge of a graph that joins a vertex to itself is called a loop
or self-loop.
• Parallel Edges: If in a directed or undirected graph, certain pair of
vertices are joined by more than one edge, such edges are called
parallel edges.
• Simple Graph: A graph in which there is only one edge between a pair
of vertices is called a simple graph.
• Multi Graph: A graph which contains some parallel edges is called a
multi graph.
• Pseudo Graph: A graph in which loops and parallel edges are allowed
is called a pseudo graph.
 Degree of a Vertex
The degree of a vertex in an undirected graph is the number of edges
incident with it, with the exception that a loop at a vertex contributes
twice to the degree of that vertex.
• The degree of vertex 𝒗 is denoted by 𝒅𝒆𝒈 𝒗 .
• The degree of an isolated vertex is zero.
• If the degree of a vertex is one, it is called a pendant vertex.
Example :
Find the degree of all vertices in the given undirected simple
graph
𝒅𝒆𝒈 (𝑽𝟏) = 𝟐
𝒅𝒆𝒈 (𝑽𝟐) = 𝟑
𝒅𝒆𝒈 (𝑽𝟑) = 𝟑
𝒅𝒆𝒈 (𝑽𝟒) = 𝟏
𝒅𝒆𝒈 (𝑽𝟓) = 𝟑
𝒅𝒆𝒈 (𝑽𝟔) = 𝟐
𝒅𝒆𝒈 (𝑽𝟕) = 𝟎

𝒗𝟒 is a pendant vertex, 𝒗𝟕 is an isolated vertex

• In-degree: In a directed graph, the number of edges with 𝒗 as their
terminal vertex (the number of edges that converge at 𝒗 ) is called the
in-degree of 𝒗 and is denoted as 𝒅𝒆𝒈− (𝒗) .
• Out-degree: In a directed graph, the number of edges with 𝒗 as their
initial vertex (the number of edges that emanate at 𝒗 ) is called the
out-degree of 𝒗 and is denoted as 𝒅𝒆𝒈+ (𝒗) .
• A vertex with zero in-degree is called a source and a vertex with zero
out-degree is called a sink.
• Example:
Find the in-degree and out-degree of the given directed graph 𝑮.
• Complete Graph: A simple graph, in which there is exactly one edge
between each pair of distinct vertices is called a complete graph. The
complete graph on 𝒏 vertices is denoted by 𝑲𝒏.
𝒏(𝒏−𝟏)
Note : The number of edges in 𝒌𝒏 is 𝒏𝒄𝟐 or . Hence, the
𝟐
𝒏(𝒏−𝟏)
maximum number of edges in a simple graph with 𝒏 vertices is .
𝟐
 Regular Graph
• If every vertex of a simple graph has the same degree, then the graph
is called a regular graph.
• If every vertex in a regular graph has degree 𝒏, then the graph is
called 𝒏 − 𝒓𝒆𝒈𝒖𝒍𝒂𝒓 graph.
Note : Any complete graph is regular, but any regular graph is not
complete graph.
 Cycles or Circuits
• If every vertex of a simple graph is of degree 𝟐, then the graph is
called a cycle or cyclic graph or circuit.
• A cycle with 𝒏 vertices is denoted by 𝑪𝒏, 𝒏 ≥ 𝟑.
• A cyclic graph is a 𝟐 − 𝒓𝒆𝒈𝒖𝒍𝒂𝒓 graph.
 Wheel Graph
Wheel graph 𝑾𝒏(𝒏 ≥ 𝟑) is obtained from 𝑪𝒏 by adding a vertex 𝒗
inside 𝑪𝒏 and connecting 𝒗 to every vertex of 𝑪𝒏 by new edges.
Note : Wheel graphs are not regular graphs and not complete
graphs.
 Bipartite Graph
• If the vertex set 𝑽 of a simple graph 𝑮 = (𝑽, 𝑬) can be partitioned into
two subsets 𝑽𝟏 and 𝑽𝟐 such that every edge of 𝑮 connects a vertex
in 𝑽𝟏 and a vertex in 𝑽𝟐 (so that no edge in 𝑮 connects either two
vertices in 𝑽𝟏 or two vertices in 𝑽𝟐 ), then 𝑮 is called Bipartite graph.
 Completely Bipartite Graph
• If every vertex of 𝑽𝟏 is connected with every vertex of 𝑽𝟐 by an edge,
then the graph 𝑮 is called a completely bipartite graph.
• If 𝑽𝟏 contains 𝒎 vertices and 𝑽𝟐 contains 𝒏 vertices, then the
completely bipartite graph is denoted by 𝑲𝒎,𝒏.
Handshaking theorem (Lemma)
[Link] and prove Handshaking theorem.
Statement:
Let 𝑮 = (𝑽, 𝑬) be a graph and let 𝒆 denote the number of edges
and let 𝒗𝟏, 𝒗𝟐, … , 𝒗𝒏 be 𝒏 vertices,
Then, σ𝒏𝒊=𝟏 𝒅𝒆𝒈 𝒗𝒊 = 𝟐 𝒆
Proof:
Since every edge is incident with exactly two vertices, every edge
contributes 𝟐 to the sum of the degree of the vertices.
Therefore, all the 𝒆 edges contribute 𝟐𝒆 to the sum of the
degree of the vertices.
Hence, σ𝒏𝒊=𝟏 𝒅𝒆𝒈 𝒗𝒊 = 𝟐 𝒆.
2. Prove that in any graph 𝑮, the number of vertices of odd degree is even.
Solution:
Let 𝑮 = (𝑽, 𝑬) be the undirected graph. Let 𝑽𝟏 and 𝑽𝟐 be the sets of
vertices of 𝑮 of even and odd degrees respectively.
Then by Handshaking theorem, we have
σ𝒗𝒊∈𝑽𝟏 𝒅𝒆𝒈 𝒗𝒊 + σ𝒗𝒋∈𝑽𝟐 𝒅𝒆𝒈 𝒗𝒋 + = 𝟐……(1)

Since each 𝒅𝒆𝒈 (𝒗𝒊) is even, σ𝒗𝒊∈𝑽𝟏 𝒅𝒆𝒈 𝒗𝒊 is even.

As the R.H.S of (1) is even, we haveσ𝒗𝒋∈𝑽𝟐 𝒅𝒆𝒈 𝒗𝒋 is even.
Since each 𝒅𝒆𝒈(𝒗𝒋) is odd, the number of terms contained in
σ𝒗𝒋∈𝑽𝟐 𝒅𝒆𝒈 𝒗𝒋 or in 𝑽𝟐 is even.
➢Hence, the number of vertices of odd degree is even.
1. Find the maximum number of edges in a simple graph with 𝒏
vertices.
2. Show that there does not exist a graph with 𝟓 vertices with
degrees 𝟏 , 𝟑 , 𝟒 , 𝟐 , 𝟑 respectively.
3. How many edges are there in a graph with 𝟏𝟎 vertices each of
degree 𝟓?
4. If a graph contains 𝟐𝟏 edges , 𝟑 vertices of degree 𝟒 and other
each of degree 𝟑 , how many vertices do the graphs has?
Questions on Bipartite Graph
1. Determine which of the following graphs are bipartite and which
are not. If a graph is bipartite, state if it is completely bipartite.

2. Define bipartite graph. Show that if 𝑮 is bipartite simple graph with

𝒑𝟐
𝒑 vertices and 𝒒 edges then 𝒒 ≤ .
𝟒
 Sub Graph
Subgraph:
A graph 𝑯 = (𝑽 ′,𝑬 ′) is called a sub graph of 𝑮 (𝑽, 𝑬) if 𝑽 ′ ⊆ 𝑽
and 𝑬 ′ ⊆ 𝑬.
Proper Subgraph:
If 𝑽 ′ ⊂ 𝑽 and 𝑬 ′ ⊂ 𝑬, then 𝑯 is called a proper subgraph of 𝑮.
Spanning Subgraph:
If 𝑽 ′ = 𝑽 , then 𝑯 is called a spanning subgraph of 𝑮. A spanning
subgraph of 𝑮 need not contain all its edges.
Any subgraph of a graph 𝑮 can be obtained by removing certain
vertices and edges from 𝑮. It is to be noted that the removal of an edge
does not go with the removal of its adjacent vertices, whereas the
removal of a vertex goes with the removal of any edge incident on it.
• Vertex deleted Subgraph: If we delete a subset 𝑼 of 𝐕 and all the
edges incident on the elements of 𝑼 from a graph 𝑮 = (𝑽, 𝑬) then the
subgraph (𝑮 − 𝑼) is called a vertex deleted subgraph of 𝑮.
• Edge deleted Subgraph: If we delete a subset 𝑭 of 𝑬 from a graph
𝑮=(𝑽, 𝑬) , then the subgraph (𝑮 − 𝑭) is called an edge deleted
subgraph of 𝑮.
• Induced Subgraph: A subgraph 𝑯 = (𝑽′,𝑬′) of 𝑮=(𝑽,𝑬) where 𝑽′⊆𝑽
and 𝑬 ′ consists of only those edges that are incident on the elements
of 𝑽′ is called an induced subgraph of 𝑮.
Example:
Draw the complete graph 𝑲𝟓 with vertices 𝑨 , 𝑩 , 𝑪 , 𝑫 , 𝑬. Draw all
complete subgraph of 𝑲𝟓 with 𝟒 vertices.
Solution : The complete graph 𝑲𝟓 with vertices 𝑨 , 𝑩 , 𝑪 , 𝑫 , 𝑬 is given
by:

The complete subgraph of 𝑲𝟓 with 𝟒 vertices are

 MATRIX REPRESENTATION OF GRAPHS
ADJACENT MATRIX:
Let 𝑮 be a simple graph with 𝒏 vertices 𝒗𝟏, 𝒗𝟐, 𝒗𝟑, … , 𝒗𝒏, then the
matrix 𝑨 (𝒐𝒓 𝑨𝑮) ≡ [𝒂𝒊𝒋] where

is called the adjacency matrix of 𝑮.

Basic properties of adjacency matrix:
1. Since a simple graph has no loops, each diagonal entry of 𝑨 (i.e) 𝒂𝒊𝒊 = 𝟎
for 𝒊 = 𝟏, 𝟐, … 𝒏.
2. The adjacency matrix of simple graph is symmetric 𝒂𝒊𝒋 = 𝒂𝒋𝒊 since both
of these entries are 𝟏 when 𝒗𝒊 and 𝒗𝒋 are adjacent and both are zero
otherwise.
3. Conversely, given any symmetric zero one matrix 𝑨 which contains
only 𝟎 ′𝒔 on its diagonal, there exists a simple graph 𝑮 whose adjacency
matrix is 𝑨.
4. 𝒅𝒆𝒈(𝒗𝒊) is equal to the number of 𝟏′𝐬 in the 𝒊𝒕𝒉 row or 𝒊𝒕𝒉 column.
Example: Find the adjacency matrix for the following graph 𝑮.

Solution: The adjacency matrix of the graph 𝑮 is given by

Problems:
1. Find the adjacency matrix for the given pseudograph.

2. Find the adjacency matrix of the following graph (unsymmetric).

Incidence Matrix:
Let 𝑮 = 𝑽, 𝑬 be an undirected simple graph with 𝒏 vertices 𝒗𝟏, 𝒗𝟐, 𝒗𝟑, …
, 𝒗𝒏 and 𝒎 edges 𝒆𝟏, 𝒆𝟐, 𝒆𝟑, … , 𝒆𝒎, then the 𝒏 × 𝒎 matrix 𝑩=[𝒃𝒊𝒋]
where

is called the incidence matrix of 𝑮.

Basic properties of incidence matrix:
1. Each column of 𝑩 contains exactly two-unit entries.
2. A row with all zero entries corresponds to an isolated vertex.
3. A row with a single unit entry corresponds to a pendant vertex.
4. 𝒅𝒆𝒈(𝒗𝒊) is equal to the number of 𝟏′𝒔 in the 𝒊𝒕𝒉 row.
1. Find the incidence matrix of the graph G.

2. Find the incidence matrix of the following pseudograph.

Path
A path in a graph is a finite alternating sequence of vertices and edges,
beginning and ending with vertices, such that each edge is incident on the vertices
preceding and following it.
If the edges in a path are distinct, then the path is called a simple path.
In the given graph, 𝒗1e1𝒗2e2𝒗3e5𝒗1e1𝒗2 is a path since it contains the edge e1
twice.
𝒗1e4𝒗4e6𝒗2e2𝒗3e7𝒗5 is a simple path as no edges appears more than once. The
number of edges in a path is called the length of the path.
 Circuit or Cycle
If the initial and final vertices of a path are the same, then the path is called a
circuit or cycle.
If the initial and final vertices of a simple path of non – zero length are the
same, then the simple path is called a simple circuit or a simple cycle.
 Connected Graph
• An undirected graph is said to be a connected graph if there is a path
between every pair of distinct vertices of the graph.
• A graph that is not connected is called a disconnected graph.

• Clearly a disconnected graph is the union of two or more connected

subgraphs, each pair of which has no vertex in common. These disjoint
connected subgraphs are called the connected components of the graph.
ISOMORPHIC GRAPHS
Definition: The simple graphs G1 = (V1, E1) and G2 = (V2, E2) are
isomorphic if there is a bijection (one-to-one and onto function) f from V1 to V2
with the property that a and b are adjacent in G1 if and only if f(a) and f(b) are
adjacent in G2, for all a and b in V1.
•Such a function f is called an isomorphism.
•In other words, G1 and G2 are isomorphic if their vertices can be ordered in such a
way that the adjacency matrices MG1 and MG2 are identical.
•From a visual standpoint, G1 and G2 are isomorphic if they can be arranged in such
a way that their displays are identical (of course without changing adjacency).
•Unfortunately, for two simple graphs, each with n vertices, there are n! possible
isomorphisms that we have to check in order to show that these graphs are
isomorphic.
•However, showing that two graphs are not isomorphic can be easy.
ISOMORPHIC GRAPHS
•For this purpose, we can check invariants, that is, properties that two isomorphic
simple graphs must both have.
•For example, they must have
➢ the same number of vertices,
➢ the same number of edges, and
➢ the same degrees of vertices.
➢ The adjacency matrices of the graph are same
➢ The number of circuits of certain length must be equal.
➢ The subgraphs generated by identical vertices are same.
•Note that two graphs that differ in any of these invariants are not isomorphic, but
two graphs that match in all of them are not necessarily isomorphic.
ISOMORPHISM AND ADJACENCY MATRICES

We state two theorems (without proof) which will help us to prove that two
labeled graphs are isomorphic.
Theorem 1:
Two graphs are isomorphic if and only if their vertices can be labeled in such a way
that the corresponding adjacency matrices are equal.
Theorem 2 :
Two labelled graphs G1 and G2 With adjacency matrices A1 and A2 Are isomorphic
if and only if, there exists a permutation matrix such that 𝑷𝑨𝟏 𝑷𝑻 = 𝑨𝟐 .
Note : A matrix whose rows are the rows of the unit matrix, but not
necessarily in their natural order is called a permutation matrix.
Problems:
1. Examine whether the following pair of graphs are isomorphic. If not
isomorphic, give the reasons.
CIRCUITS AND ISOMORPHISM
• Apart from the three invariants of two isomorphic graphs already discussed,
namely number of vertices, number of edges and degrees of corresponding
vertices, we have one more invariant of isomorphic graphs.
• If the two graphs are isomorphic, they will contain circuits of the same length k
where k > 2.
• If this invariant condition is not satisfied then the two graphs will not be
isomorphic.
Example: Show that following graphs G and 𝑯 are not isomorphic.
• The number of circuits of length 4 in both the graphs G and H are not same.
Hence, the two graphs G and H are not isomorphic graphs.
1. Are the simple graphs with the following adjacency matrices
isomorphic?

2. Establish the isomorphic for the following graphs.

• Problem: Show that if a graph with 𝒐 vertices is self complementary then
n ≡ 0 or 1 (mod 4).
 Eulerian Graph
• Eulerian path: A path of a graph G is called a Eulerian path, if it includes each
edge of G exactly once.
• Eulerian Circuit: A circuit of a graph G is called a Eulerian circuit, if it includes
each edge of G exactly once.
• Eulerian Graph: A graph containing a Eulerian circuit is called a Eulerian graph.
 Hamiltonian Graph
• Hamiltonian path: A path of a graph 𝑯 is called a Hamiltonian path, if it includes
each vertex of 𝑯 exactly once.
• Hamiltonian Circuit: A circuit of a graph 𝑯 is called a Hamiltonian circuit, if it
includes each vertex of 𝑯 exactly once.
• Hamiltonian Graph: A graph containing a Hamiltonian circuit is called a
Hamiltonian graph.
 Properties

• From the graph shown above, it is clear that the path obtained by deleting any one
edge from a Hamiltonian circuit is a Hamiltonian path.
• Also, a Hamiltonian circuit contains a Hamiltonian path, but a graph containing a
Hamiltonian path need not have a Hamiltonian circuit.
• A complete graph 𝑲n will always have a Hamiltonian circuit, when n ≥ 3, due to
the fact that an edge exists between any two vertices and a circuit can be formed
by beginning at any vertex and by visiting the remaining vertices in any order.
• A given graph may contain more than one Hamiltonian circuit.
 Shortest Path Problems
• What are the Shortest Path Algorithms?
The shortest path algorithms are the ones that focuses on calculating the minimum
travelling cost from source node to destination node of a graph in optimal time
and space complexities.
• Types of Shortest Path Algorithms:
• As we know there are various types of graphs (weighted, unweighted, negative,
cyclic, etc.) therefore having a single algorithm that handles all of them efficiently
is not possible.
• In order to tackle different problems, we have different shortest-path algorithms,
which can be categorized into two categories:
➢ Single Source Shortest Path Algorithms:
➢ All Pair Shortest Path Algorithms:
(Note: for our course we are only dealing with 1st category)
• Single Source Shortest Path Algorithms:
In this algorithm we determine the shortest path of all the nodes in the graph with
respect to a single node i.e. we have only one source node in this algorithms.
(* before moving forward some concept of tree is required)
TREE
A tree is a special type of graph that is connected and acyclic, meaning it
has no cycles or loops.
It consists of nodes (vertices) and edges (connections between nodes), where there is
exactly one path between any two nodes.
Properties of Trees
A tree has several defining properties, which are important in understanding
its behavior and characteristics. These include the following −
• Connectivity: A tree is a connected graph, meaning there is a path between any
two vertices. Unlike general graphs, trees have no isolated vertices.
• Acyclic Nature: A tree is acyclic, meaning it does not contain any cycles. This is
one of the defining characteristics of a tree, distinguishing it from general graphs.
• Number of Edges: For a tree with n vertices, there are always n-1 edges. This is a
fundamental property of trees and is used in algorithms involving trees.
• Leaf Nodes: A leaf in a tree is a vertex that has only one edge connected to it
(also known as a terminal vertex). A tree can have one or more leaf nodes.
• Rooted Trees: A tree can be considered as a rooted tree if one vertex is
designated as the "root," and all edges have a direction pointing away from this
root. In a rooted tree, the hierarchy is clearly defined, and each vertex has a parent
and potentially multiple children.
• Subtrees: Any tree can be divided into smaller trees by removing edges. A subtree is a
part of a tree that is itself a tree, consisting of a vertex and all its descendants.
• Depth of a Tree: The depth of a tree is the length of the longest path from the root to any
leaf. The depth of a tree gives insight into its hierarchy and is important for various tree-
based algorithms.
• Height of a Tree: The height of a tree is the number of edges on the longest path from
the root to any leaf. The height is a measure of the longest possible chain of nodes in the
tree.
• Level of a Node: The level of a node is defined by its distance from the root. The root is
at level 0, its direct children are at level 1, and so on.
• Balanced Trees: A tree is said to be balanced if the height difference between the left
and right subtrees of any node is minimal (usually no greater than 1). Balanced trees are
important for performance optimization in search operations.
• Height Balanced and Weight Balanced Trees: Height-balanced trees are those where
the difference in heights of subtrees of any node is bounded by a constant (commonly 1).
• Weight-balanced trees ensure that the number of nodes in the left and right subtrees of
any node is approximately equal.
• Forest: A forest is a disjoint collection of trees. If you remove any edge from a tree, the
graph becomes a forest. Each connected component in a forest is a tree
Binary Tree
• A binary tree is a tree where each node has at most two children. Binary trees
are widely used in computer science for tasks like searching, sorting, and
hierarchical data storage.
BINARY SEARCH TREE
Shortest Path (Dijkstra's algorithm)
• Since the shortest path can be calculated from single source vertex to all the other
vertices in the graph, Dijkstra's algorithm is also called single-source shortest
path algorithm. The output obtained is called shortest path spanning tree.
• Dijkstra’s algorithm is an iterative procedure that finds the shortest path between
two vertices S and V in a weighted graph.
• It proceeds by finding the length of the shortest path from S to successive vertices
and adding these vertices to a distinguished set of vertices V.
• The algorithm terminates once it reaches the vertex V.
Algorithm:
❑Assign every node an initial distance (0 to the source, ∞for all
others); mark all nodes as unvisited
❑While there are unvisited nodes:
➢select unvisited node with smallest distance (current)
➢consider all unvisited neighbors of current node:
• compute distance to each neighbor from current node
• if less than current distance, replace with new distance
➢mark current node as visited (and never evaluate again)
Dijkstra example:
VERTEX S A B C D E
DISTANCE 0 ∞ ∞ ∞ ∞ ∞
S 6 ∞ ∞ 8 7
A 15 ∞ 8 7
E 15 12 8
D 15 11
C 15
B 0 6 15 11 8 7