Academic Year : 2025-2026
Year & Semester : II-I
Department : CSE
Course Title & Code : DMGT 24ALBTHS305T
Micro Project Title: Graph Isomorphism &
Subgraphs
Name of Student; Roll No : V. Tejaswini
242G1A05L3.
Faculty Name: K. KARISHMA TAJ
Abstract:
This micro-project investigates graph isomorphism and subgraph
detection problems. It covers definitions, theoretical properties, and
practical algorithms for identifying whether two graphs are
isomorphic and whether one graph contains another as a subgraph
(including induced subgraphs). You will implement and compare at
least two algorithms for each problem (e.g., Nauty/Weisfeiler–
Lehman labeling, VF2 for subgraph isomorphism, and a
brute-force/backtracking baseline). Experiments will use synthetic
and small real-world graph instances, measure runtime and accuracy,
and analyze complexity and limitations. The deliverable includes a
short report, source code, sample results, and a presentation.
Introduction:
Graph theory is an essential branch of discrete mathematics that helps
represent and analyze relationships between objects. Two important
concepts in this field are Graph Isomorphism and Subgraphs.
Graph isomorphism focuses on identifying whether two graphs are
structurally the same, while subgraphs deal with smaller parts of a
graph that preserve connections among selected vertices.
Understanding these concepts is crucial for applications in network
analysis, chemistry (molecular structures), computer networks, and
pattern recognition.
Graph Isomorphism: Two graphs ( G_1(V_1, E_1) ) and
( G_2(V_2, E_2) ) are said to be isomorphic if there exists a
one-to-one correspondence between their vertices such that the
adjacency (connectivity) between vertices is preserved.
Subgraph: A graph ( H(V_H, E_H) ) is a subgraph of ( G(V, E)
) if ( V_H \subseteq V ) and ( E_H \subseteq E ). It represents a
portion of the main graph while maintaining the structure among
selected nodes and edges.
Examples:
Example 1: Graph Isomorphism
Consider two graphs:
Graph G1: Vertices = {A, B, C}, Edges = {(A, B), (B, C), (C, A)}
Graph G2: Vertices = {1, 2, 3}, Edges = {(1, 2), (2, 3), (3, 1)}
Both represent a triangle, so there exists a one-to-one mapping (A→1, B→2,
C→3) that preserves adjacency. Hence, G1 and G2 are isomorphic.
Example 2: Subgraph
Consider a graph G with vertices {A, B, C, D} and edges {(A, B), (B, C), (C,
D), (A, D)}. A subgraph H can be formed by selecting vertices {A, B, C} and
edges {(A, B), (B, C)}. This H is a subgraph of G.
Real-World Examples:
1. Chemistry (Molecular Graphs)
Molecules can be represented as graphs where atoms are
vertices and bonds are edges. Two molecules are isomorphic if
their molecular graphs are identical in structure (e.g., isomers
like ethanol and dimethyl ether can be compared through graph
isomorphism).
2. Computer Networks
In network design, graph isomorphism helps detect identical
topologies between two network layouts. Subgraphs represent
subnetworks, such as LANs within a larger WAN.
3. Social Networks
In social media graphs (like Facebook or Instagram networks),
users are vertices and friendships are edges. Detecting
subgraphs can identify communities or friend circles, while
isomorphism helps detect similar social structures across
platforms.
4. Pattern Recognition and Image Processing
In computer vision, objects are represented as graphs of
connected features. Detecting if a smaller object appears in a
larger image involves subgraph isomorphism.
5. Biological Networks
Protein interaction networks and gene regulatory networks use
graph structures. Finding common interaction patterns
corresponds to subgraph isomorphism problems.
6. Database Searching
Subgraph isomorphism is applied in querying graph databases
(like Neo4j) to find occurrences of a given pattern structure
within a larger dataset.
Types of Isomorphism:
You can explain different variations of isomorphism used in graph
theory:
Graph Isomorphism – one-to-one mapping preserving edges.
Subgraph Isomorphism – whether a smaller graph exists
within a larger one.
Automorphism – an isomorphism of a graph with itself (helps
detect symmetries).
Induced Subgraph Isomorphism – checks whether selected
vertices induce identical connections.
Algorithms Used:
Include a short section explaining algorithms used to test
isomorphism:
Brute Force (Permutation Checking)
Weisfeiler–Lehman (WL) Algorithm
VF2 Algorithm for Subgraph Isomorphism
Graph Hashing Methods
Graph Invariants:
Discuss properties that remain unchanged under isomorphism:
Degree sequence
Number of vertices and edges
Adjacency matrix
Eigenvalues of the adjacency matrix
Number of connected components
Learning Objectives:
Understand formal definitions: graph isomorphism, subgraph,
induced subgraph, automorphism.
Implement and compare algorithmic approaches for graph
isomorphism and subgraph detection.
Evaluate algorithms experimentally on datasets and analyze
time/space trade-offs.
Write a concise technical report and present findings.
References & Resources (short list):
Bondy, J.A. & Murty, U.S.R. Graph Theory (textbook).
Cordella, L., et al., VF2: An Improved Algorithm for Matching
Large Graphs (paper).
NetworkX documentation: algorithms for isomorphism and
graph hashing.
Weisfeiler–Lehman algorithm overview (lecture notes /
surveys).
Conclusion:
Graph isomorphism and subgraphs are fundamental
concepts that play a key role in graph analysis.
Isomorphism helps identify structural similarity
between graphs, while subgraphs allow focused
analysis of smaller sections within a network. These
concepts form the basis for many applications such as
pattern matching, chemical compound analysis, social
network mapping, and database indexing.
Understanding their theoretical background and
implementing algorithms to detect them strengthens
one’s foundation in discrete mathematics and graph
theory, which is essential for advanced fields like
computer science, artificial intelligence, and data
science.