See discussions, stats, and author profiles for this publication at: https://www.researchgate.

net/publication/385705466

Graph Theory: A Detailed Overview

Article · November 2024

CITATIONS READS
0 168

3 authors, including:

Mansi Khatri
Sardar Patel Institute of Technology
3 PUBLICATIONS 0 CITATIONS

SEE PROFILE

All content following this page was uploaded by Mansi Khatri on 11 November 2024.

The user has requested enhancement of the downloaded file.

 Graph Theory: A Detailed Overview
Mansi Khatri- 2023200068
Qasim Khan- 2023200068
Niraj Mahajan - 2023200074

Graph theory is a branch of discrete mathematics that studies the relation-

ships between pairs of objects, represented as vertices and edges. This powerful
tool models real-world problems and is widely applicable in computer science,
biology, social networks, economics, transportation, and beyond.

1 Basic Concepts
A graph G = (V, E) consists of:
• V is a set of vertices, also called nodes, which represent the objects or
entities.

• E is a set of edges, also called links, representing the relationships between

the vertices.
Graphs are classified into different types based on their structural properties:
• Directed Graphs (Digraphs): The edges have a direction, indicating
the relationship flows from one vertex to another. For an edge (u, v),
u → v.
• Undirected Graphs: In an undirected graph, edges are bidirectional.
The edge {u, v} indicates a mutual relationship between u and v.
• Weighted Graphs: In these graphs, each edge is associated with a weight
(or cost), representing a quantity like distance, time, or capacity.
• Unweighted Graphs: Here, edges have no associated weights, and only
the existence of connections matters.
Graphs can also be categorized based on their vertex and edge configurations:

• Simple Graph: A graph without multiple edges (parallel edges) or self-

loops (edges connecting a vertex to itself).
• Multigraph: A graph that allows multiple edges between the same pair
of vertices.

1
 • Complete Graph: A graph where every pair of distinct vertices is con-
nected by a unique edge.
• Bipartite Graph: A graph in which the vertices can be divided into
two distinct sets U and V , such that edges only exist between vertices in
different sets.

Figure 1: Types of graphs

Figure 2: Bipartite graph

2 Graph Traversal: Exploring Graphs

Graph traversal refers to visiting all the vertices of a graph in a specific manner.
This is a fundamental operation in graph theory, allowing us to explore its
structure and properties.

2.1 Breadth-First Search (BFS)

BFS is an algorithm for exploring vertices layer by layer, expanding outward
from the starting vertex. It systematically visits all neighboring vertices before
moving on to the next level. A queue is used to track the vertices to be visited.
Steps:

2
 1. Start at a specified vertex, enqueue it, and mark it as visited.
2. Dequeue a vertex, visit its unvisited neighbors, and enqueue them.
3. Repeat the process until the queue is empty.
Properties of BFS:
• BFS is useful for finding the shortest path in unweighted graphs, as the
first time a vertex is reached guarantees it’s via the shortest path.
• It explores vertices level by level, making it ideal for problems requiring
level-wise exploration (e.g., finding all vertices at distance k from the
starting node).
• The space complexity of BFS is O(V ) due to the storage of vertices in the
queue.

Algorithm 1 Breadth-First Search (BFS)

Require: Graph G = (V, E), source vertex s
Ensure: BFS traversal order and shortest path from s to all reachable vertices
1: Initialize an empty queue Q
2: Initialize all vertices as unvisited
3: Set the distance d[s] = 0
4: Mark s as visited and enqueue it into Q
5: while Q is not empty do
6: Dequeue a vertex u from Q
7: for each neighbor v of u do
8: if v is unvisited then
9: Mark v as visited
10: Set d[v] = d[u] + 1
11: Enqueue v into Q
12: end if
13: end for
14: end while

2.2 Depth-First Search (DFS)

DFS is an algorithm that explores as deep as possible along each branch before
backtracking. A stack (or recursion) is used to push vertices as they are visited
and to pop them when backtracking.
Steps:
1. Start at a specified vertex, push it onto the stack, and mark it as visited.
2. Visit the next unvisited neighbor, push it onto the stack, and repeat until
no unvisited neighbors remain.

3
 3. Backtrack by popping vertices from the stack.
Properties of DFS:
• DFS is often used in topological sorting, detecting cycles in directed
graphs, and solving maze-like problems.

• Unlike BFS, DFS does not guarantee the shortest path, as it explores
deeply before checking all neighbors.
• The space complexity of DFS is O(V ) in the worst case due to recursion
depth.

Algorithm 2 Depth-First Search (DFS)

Require: Graph G = (V, E), starting vertex s
Ensure: DFS traversal order of the graph from s
1: Mark s as visited
2: Initialize an empty stack S
3: Push s onto S
4: while S is not empty do
5: Pop a vertex u from S
6: for each neighbor v of u do
7: if v is unvisited then
8: Mark v as visited
9: Push v onto S
10: end if
11: end for
12: end while

2.3 Time Complexity

The time complexity of both BFS and DFS is O(V + E), where V is the number
of vertices and E is the number of edges. This linear complexity ensures both
algorithms are efficient even for large graphs.

3 Matching in Graphs
Matching problems involve finding a set of edges in a graph such that no two
edges share a common vertex. Matching is particularly useful in bipartite graphs
where two distinct sets of vertices (e.g., workers and jobs) are matched based
on a relationship.

4
3.1 Types of Matching
• Maximum Matching: A matching that contains the largest possible
number of edges.
• Perfect Matching: A matching where every vertex in the graph is in-
cluded in exactly one edge.
• Stable Matching: In some cases (e.g., the marriage problem), the goal
is to find a matching where no two vertices would prefer to be matched
with each other over their current matches.

Applications of Matching:
• Matching is used in resource allocation problems, like assigning jobs to
workers or pairing students with mentors.
• In network flow problems, maximum matching is used to optimize the
distribution of resources across a network.
• Stable matching algorithms, such as the Gale-Shapley algorithm, are used
in pairing applications, like matching medical residents to hospitals.

4 Graph Representations
A graph can be represented in different ways, each suited for different compu-
tational needs.

4.1 Adjacency Matrix

An adjacency matrix is a n × n matrix where n is the number of vertices. The
entry A[i][j] is 1 if an edge exists between vertices i and j, and 0 otherwise.
 
0 1 0 0
1 0 1 1
A= 0 1 0 1


0 1 1 0
This representation is most efficient for dense graphs, where many edges are
present. The space complexity is O(n2 ), which can be excessive for large sparse
graphs.

4.2 Adjacency List

In this representation, each vertex maintains a list of its adjacent vertices. It is
a space-efficient way to represent sparse graphs, using O(V + E) space.
Example of adjacency list for a simple undirected graph:

1 → [2]

5
 2 → [1, 3, 4]
3 → [2, 4]
4 → [2, 3]
This representation allows for efficient edge insertion and deletion, making
it suitable for dynamic graphs.

4.3 Edge List

An edge list is simply a collection of all edges in the graph, stored as pairs of
vertices. This representation is useful when the graph is small and edge-centric
operations are needed.
Example of an edge list:

E = {(1, 2), (2, 3), (2, 4), (3, 4)}

Each representation has its own benefits and drawbacks in terms of time and
space complexity, depending on the size and sparsity of the graph.

5 Eulerian and Hamiltonian Paths

5.1 Eulerian Path
An Eulerian path visits every edge of the graph exactly once. An Eulerian
circuit is an Eulerian path that starts and ends at the same vertex.
Euler’s Theorem states that a graph contains an Eulerian Circuit if and
only if every vertex has an even degree, and all vertices with non-zero degree
are connected. Examples:
• The famous Eulerian circuit in the Seven Bridges of Königsberg problem
was solved by Euler himself, proving that no such path exists.
• A simple example of an Eulerian circuit can be found in a square with
diagonals, where each vertex has even degree.

Figure 3: Eulerian Path

6
5.2 Hamiltonian Path
A Hamiltonian path visits every vertex of a graph exactly once. A Hamiltonian
cycle is a Hamiltonian path that starts and ends at the same vertex. Unlike
Eulerian paths, determining the existence of a Hamiltonian path is NP-complete,
making it computationally difficult. Applications of Hamiltonian Paths:
• The Traveling Salesman Problem (TSP) is a classic example, where the
goal is to find the shortest possible route that visits each city exactly once
and returns to the origin city.
• Hamiltonian cycles have applications in circuit design, scheduling, and
vehicle routing problems.

Figure 4: Example of a Hamiltonian cycle problem.

7
6 Applications of Graph Theory
Graph theory has a wide range of applications across various fields, including
computer science, operations research, biology, and social sciences. Here are
some prominent examples:

• Computer Networks and Communication: Graphs are used to model

networks, where nodes represent devices, and edges represent communi-
cation links. Algorithms related to shortest paths, connectivity, and flow
are crucial for efficient data routing and network optimization.

• Social Networks: Graphs help model relationships between individuals.

Analysis of these graphs can reveal key influencers, community structures,
and paths of information dissemination.
• Scheduling and Timetabling: Graph coloring is applied to schedule
problems, ensuring that no two conflicting tasks overlap in time (e.g.,
exam scheduling where no student has overlapping exams).
• Biology and Chemistry: Graphs are used to represent molecular struc-
tures, pathways in metabolic networks, and protein interactions, aiding in
drug discovery and the study of diseases.
• Transportation and Logistics: Graph algorithms help solve routing
problems (e.g., Dijkstra’s or Bellman-Ford for shortest paths), improve
traffic flow management, and optimize delivery routes.
• Circuit Design and Electrical Engineering: Hamiltonian and Eule-
rian paths find applications in circuit board layout, minimizing the cost
of connections, and designing efficient layouts.

• Robotics and Artificial Intelligence: Path finding algorithms in graphs,

such as A* and Dijkstra’s, are fundamental for autonomous navigation and
motion planning.

8
7 Solved Example:

Figure 5: Caption

Both G and H have six vertices and seven edges. Both have four vertices of
degree two and two vertices of degree three. It is also easy to see that the
subgraphs of G and H consisting of all vertices of degree two and the edges
connecting them are isomorphic (as the reader should verify). Because G and
H agree with respect to these invariants, it is reasonable to try to find an iso-
morphism.
We now will define a function f and then determine whether it is an isomor-
phism .Because deg(u1)=2 and because u1 is not adjacent to any other vertex
of degree two,the image of u1 must be either v4 or v6,the only two vertices
of degree two in H not adjacent to a vertex of degree two.We arbitarily set
f(u1)=v6.[If we found that this choice did not lead to isomorphism,we would then
try f(u1)=v4.]Because u2 is adjacent to u1,the possible images of u2 are v3 and
v5.We arbitarily set f(u2)=v3.Continuing in this way,using adjacency of vertices
and degrees as a guide,we set f(u3)=v4,f(u4)=v5,f(u5)=v1 and f(u6)=v2.We
now have a one-to-one correspondance between the vertex set of G and the ver-
tex set of H,namely f(u1)=v6,f(u2)=v3,f(u3)=v4,f(u4)=v5,f(u5)=v1,f(u6)=v2.To

9
 see whether f preserves edges ,we examine the adjacency matrix of G,

u1 u2 u3 u4 u5 u6
u1 0 1 0 1 0 0
u2 1 0 1 0 0 1
AG = u 3 0 1 0 1 0 0 ,
u4 1 0 1 0 1 0
u5 0 0 0 1 0 1
u6 0 1 0 0 1 0

and the adjacency of matrix H with the rows and columns labeled by the images
of the corresponding vertices in G,

u1 u2 u3 u4 u5 u6
u1 0 1 0 1 0 0
u2 1 0 1 0 0 1
AH = u3 0 1 0 1 0 0
u4 1 0 1 0 1 0
u5 0 0 0 1 0 1
u6 0 1 0 0 1 0

Because AG = AH , it follows that f preserves edges.

We conclude that f is an isomorphism, so G and H are isomorphic.
Note that if f turned out not to be an isomorphism, we would not have established that G
and H are not isomorphic, because another correspondence of the vertices in G and H
may be an isomorphism.

8 Conclusion
Graph theory is a rich and versatile field with significant implications across
multiple disciplines. By providing a framework for modeling and solving com-
plex problems, it has become indispensable in research and practical problem-
solving. The study of graphs, their properties, and their real-world applications
empowers us with tools to address challenges in fields ranging from computer
science to transportation networks and biological systems.

9 References
Introduction to Graph Theory - By Richard D Trudeau
Discrete Mathematics - By Rosen

10

View publication stats