This interactive simulation introduces the fundamental concepts of Graph Theory, a branch of discrete mathematics that studies the relationships between objects. Graphs are used extensively in computer science, network analysis, social sciences, biology, and optimization problems.

What is a Graph?

A graph G = (V, E) consists of:

• V (Vertices/Nodes): A set of objects or entities
• E (Edges): A set of connections between pairs of vertices

Graphs model relationships such as: social networks (people connected by friendships), road maps (cities connected by roads), web pages (linked by hyperlinks), and molecular structures (atoms connected by bonds).

Graph Types

Type	Definition	Example
Undirected Graph	Edges have no direction. If A is connected to B, then B is also connected to A.	Friendship networks, road maps (two-way streets)
Directed Graph (Digraph)	Edges have direction (arrows). Edge from A to B doesn't imply edge from B to A.	Twitter followers, web links, one-way streets
Weighted Graph	Each edge has an associated numerical value (weight).	Road networks (distance), network bandwidth, costs
Complete Graph (Kn)	Every pair of distinct vertices is connected by an edge.	Full connectivity, round-robin tournaments

Graph Representations

There are several ways to represent graphs mathematically and in computer memory:

Representation	Description	Size
Adjacency Matrix (A)	V×V matrix where A[i][j] = 1 if edge exists from i to j, 0 otherwise. Symmetric for undirected graphs. For weighted graphs, stores edge weights.	O(V²)
Incidence Matrix (B)	V×E matrix where B[v][e] = 1 if vertex v is incident to edge e. For directed graphs: +1 if edge leaves v, -1 if edge enters v.	O(V×E)
Degree Matrix (D)	V×V diagonal matrix where D[i][i] = degree of vertex i. All off-diagonal entries are zero.	O(V²)
Laplacian Matrix (L)	L = D - A (Degree minus Adjacency). Key property: Row sums = 0. Used in spectral graph theory, graph partitioning, and network analysis.	O(V²)
Adjacency List	Array of lists where the i-th list contains all neighbors of vertex i. More space-efficient for sparse graphs.	O(V + E)

Vertex Degree

The degree of a vertex is the number of edges connected to it:

Handshaking Lemma: In any undirected graph, the sum of all vertex degrees equals twice the number of edges:

Special Vertices

• Isolated Vertex: A vertex with degree 0 (no edges)
• Pendant/Leaf: A vertex with degree 1 (exactly one edge)
• Hub/Celebrity: A vertex with very high degree relative to others

Graph Isomorphism

Two graphs G₁ and G₂ are isomorphic if there exists a one-to-one mapping between their vertices that preserves edge connections. In other words, they have the same structure but may look different when drawn.

Common Graph Structures

Structure	Definition	Properties
Path (Pn)	n vertices connected in a line	n-1 edges, 2 leaves, no cycles
Cycle (Cn)	n vertices forming a closed loop	n edges, every vertex has degree 2
Star (Sn)	One central vertex connected to n-1 others	n-1 edges, 1 hub with degree n-1
Complete (Kn)	Every vertex connected to every other	n(n-1)/2 edges, every vertex has degree n-1
Bipartite	Vertices split into two groups, edges only between groups	No odd cycles, 2-colorable
Binary Tree	Hierarchical structure where each node has at most 2 children	n-1 edges for n nodes, no cycles, connected
Grid/Mesh	Nodes arranged in rows and columns with neighbors connected	Regular structure, used in image processing, routing
Petersen Graph	Famous 10-vertex graph: outer pentagon + inner pentagram with spokes	3-regular (every vertex has degree 3), non-planar, highly symmetric

Applications of Graph Theory

Field	Application
Computer Networks	Routing algorithms, network topology design, packet switching
Social Networks	Friend recommendations, influence propagation, community detection
Transportation	Shortest path (GPS), traffic flow, airline scheduling
Biology	Protein interaction networks, phylogenetic trees, neural networks
Web Search	PageRank algorithm, link analysis, web crawling

Simulation

The interactive simulator is below. Use the controls to explore the concepts described above.

Usage Instructions

1. Select Module: Click buttons to toggle different analysis views (click again to turn off):
   • Representations: See real-time adjacency matrix and list updates.
   • Centrality: Visualize degree distribution with dynamic histograms.
   • Isomorphism: Puzzle mode - drag nodes to prove graph equivalence.
2. Build Graphs:
   • Click empty space to add a new node
   • Drag a node to move it
   • Hold Shift and drag from one node to another to create an edge
   • Click on an edge to edit it (popup menu appears)
   • Right-click on a node or edge to delete it
   • Double-click a node to rename it
3. Edit Edges: Click on any edge to open the edit popup:
   • Weight: Change edge weight (only shown in Weighted mode)
   • Reverse: Flip edge direction A→B becomes B→A (Directed mode only)
   • Bidirectional: Add reverse edge to make it two-way (Directed mode only)
   • Delete: Remove the edge
4. Graph Properties:
   • Directed: Edges become arrows (A→B ≠ B→A)
   • Weighted: Edges have numerical weights (prompted when creating)
5. Load Presets: Select from the dropdown to load pre-built graph structures:
   • Basic: Triangle, Star, Complete (K₄), Path, Cycle
   • Structures: Binary Tree, 3×3 Grid, Bipartite, Petersen Graph
   • Real World: Social Network, Web Links, Airport Routes, Molecule
   Note: Web Links auto-enables Directed mode; Airport Routes auto-enables Weighted mode.

Preset Graph Descriptions

Preset	Description	Educational Value
Binary Tree	11-node tree with depth 3	Hierarchical data, no cycles, connected acyclic graph
Petersen Graph	Famous 10-node graph with outer pentagon + inner pentagram	3-regular graph, non-planar, used in graph theory proofs
3×3 Grid	9 nodes in mesh layout	Network topology, lattice structure, routing problems
Social Network	8-node network with hub (Alice)	Centrality, clustering, "six degrees of separation"
Web Links	8-page website structure (directed)	PageRank, link analysis, in-degree vs out-degree
Airport Routes	6-city network with weighted distances	Shortest path problems, hub-and-spoke topology
Molecule	Benzene-like structure (hexagon + hydrogens)	Chemical graph theory, molecular modeling

Module Details

📊 Representations Module

• Use the dropdown to switch between 4 matrix representations:
  • Adjacency (A): V×V matrix, A[i][j]=1 if edge from i to j
  • Incidence (B): V×E matrix, B[v][e]=1 if vertex v touches edge e
  • Degree (D): Diagonal matrix, D[i][i]=degree of vertex i
  • Laplacian (L=D-A): Used in spectral graph theory, eigenvalues reveal graph structure
• The Adjacency List shows each node and its neighbors in list format
• All representations update in real-time as you modify the graph

📈 Centrality Module

• The histogram shows degree distribution - each bar represents a node
• Bar height = node degree (number of connections)
• The Celebrity Node (highest degree) is highlighted in gold
• In directed graphs, both in-degree and out-degree contribute

🧩 Isomorphism Module

• Two graphs are shown with the same structure but different layouts
• Drag nodes in Graph A to visually match the layout of Graph B
• When positions match (within tolerance), the puzzle is solved
• This demonstrates that isomorphic graphs can look very different

Key Observations to Make

Experiment	What to Observe
Load K₄ Complete preset	Adjacency matrix is symmetric with all 1s except diagonal. Every node has degree 3.
Load Petersen Graph	Every vertex has exactly degree 3 (3-regular). Try the Laplacian matrix view!
Load Web Links preset	Directed graph auto-enabled. Matrix is NOT symmetric. Notice in-degree vs out-degree.
Load Airport Routes preset	Weighted graph auto-enabled. Matrix shows weights (1-8). Edge thickness varies.
View Incidence Matrix	Columns = edges. For directed graphs, +1 (outgoing) and -1 (incoming) are shown in red.
View Degree Matrix	Only diagonal has values. Diagonal = degree of each vertex.
View Laplacian Matrix	L = D - A. All row sums equal zero. Eigenvalues reveal connectivity!
Load Social Network + Centrality	Node A (Alice) is the celebrity hub. Histogram shows skewed degree distribution.
Solve isomorphism puzzle	Identical adjacency matrices for visually different graphs!

Matrix Color Coding

• Green - Positive values (edge exists, or positive weight)
• Red - Negative values (in Incidence matrix: incoming edge in directed graph)
• Blue - Diagonal values (in Degree/Laplacian matrix)
• Grey - Zero values

Mathematical Formulas

Algorithm Complexity Reference

Operation	Adjacency Matrix	Adjacency List
Add vertex	O(V²) - resize matrix	O(1)
Add edge	O(1)	O(1)
Remove vertex	O(V²)	O(V+E)
Remove edge	O(1)	O(degree)
Check edge exists	O(1)	O(degree)
Find all neighbors	O(V)	O(degree)
Space complexity	O(V²)	O(V+E)

When to Use Each Representation

• Adjacency Matrix: Dense graphs (many edges), frequent edge lookups, small V
• Adjacency List: Sparse graphs (few edges), need to iterate neighbors, large V

Rule of thumb: If |E| ≈ |V|² (dense), use matrix. If |E| << |V|² (sparse), use list.