Graph Theory Fundamentals
Introduction
Graphs are one of the most versatile structures in computer science. They model networks, relationships, dependencies, and connections. From social networks to GPS navigation to dependency resolution, graphs are everywhere.
Learning Objectives
By the end of this reading, you will be able to:
- Define graphs and their components
- Distinguish between graph types (directed, weighted, etc.)
- Understand graph representations in memory
- Identify special graphs and their properties
- Apply basic graph concepts to real problems
1. What is a Graph?
A graph G = (V, E) consists of:
- V: A set of vertices (or nodes)
- E: A set of edges connecting pairs of vertices
Example
A --- B
| |
| |
C --- D
V = {A, B, C, D} E = {{A,B}, {A,C}, {B,D}, {C,D}}
2. Types of Graphs
Undirected vs Directed
Undirected Graph: Edges have no direction
- Edge {u, v} = {v, u}
- Example: Facebook friendships
Directed Graph (Digraph): Edges have direction
- Edge (u, v) ≠ (v, u)
- Example: Twitter follows, one-way streets
Undirected: Directed:
A --- B A → B
↑ ↓
C ← D
Weighted vs Unweighted
Weighted Graph: Edges have associated values (weights)
- Example: Road network with distances
A --5-- B
| |
3 2
| |
C --4-- D
Simple vs Multi-graphs
Simple Graph: No loops (edge from vertex to itself), no multiple edges between same pair Multigraph: Allows multiple edges between vertices Pseudograph: Allows loops and multiple edges
Connected vs Disconnected
Connected: There's a path between every pair of vertices Disconnected: Some vertices can't reach others
Connected: Disconnected:
A --- B A --- B E --- F
| | | |
C --- D C --- D
3. Graph Terminology
Vertices and Edges
- Adjacent vertices: Connected by an edge
- Incident edge: An edge connected to a vertex
- Degree: Number of edges incident to a vertex (deg(v))
- In-degree/Out-degree: For directed graphs, edges coming in/going out
Paths and Cycles
- Path: Sequence of vertices connected by edges
- Simple path: No repeated vertices
- Cycle: Path that starts and ends at same vertex
- Simple cycle: Cycle with no repeated vertices (except start/end)
Path length: Number of edges in the path
Special Structures
- Complete graph (Kₙ): Every pair of vertices is connected
- Bipartite graph: Vertices can be split into two groups where edges only go between groups
- Tree: Connected graph with no cycles
- Forest: Collection of trees (graph with no cycles)
Complete K₄: Bipartite: Tree:
A --- B A B C A
|\ /| |\ /|\ /| /|\
| X | | X | X | B C D
|/ \| |/ \|/ \| |
C --- D D E F E
4. Graph Representations
Adjacency Matrix
A V×V matrix where entry (i,j) indicates if there's an edge from i to j.
Example:
Graph: Matrix:
A --- B A B C D
| | A [ 0 1 1 0 ]
C --- D B [ 1 0 0 1 ]
C [ 1 0 0 1 ]
D [ 0 1 1 0 ]
Properties:
- Space: O(V²)
- Check if edge exists: O(1)
- Find all neighbors: O(V)
- Good for dense graphs
For weighted graphs: Store weight instead of 1
Adjacency List
Each vertex stores a list of its neighbors.
Example:
Graph: Adjacency List:
A --- B A: [B, C]
| | B: [A, D]
C --- D C: [A, D]
D: [B, C]
Properties:
- Space: O(V + E)
- Check if edge exists: O(degree)
- Find all neighbors: O(degree)
- Good for sparse graphs
Edge List
Simply a list of all edges.
Example:
[(A,B), (A,C), (B,D), (C,D)]
Properties:
- Space: O(E)
- Simple to implement
- Efficient for edge-centric algorithms (like Kruskal's)
5. Important Graph Properties
Handshaking Lemma
In any undirected graph: Σ deg(v) = 2|E|
The sum of all degrees equals twice the number of edges (each edge contributes to two vertices' degrees).
Corollary: The number of vertices with odd degree is always even.
Trees
A tree with n vertices has exactly n-1 edges.
Properties of trees:
- Connected
- No cycles
- Exactly one path between any two vertices
- Removing any edge disconnects it
- Adding any edge creates a cycle
Bipartite Graph Test
A graph is bipartite if and only if it contains no odd-length cycles.
Test: Can be colored with 2 colors such that no adjacent vertices share a color.
6. Special Graphs
Complete Graph (Kₙ)
Every pair of vertices connected.
- Edges: n(n-1)/2
- Each vertex has degree n-1
Complete Bipartite Graph (Km,n)
Two sets of m and n vertices; every vertex in one set connects to all in the other.
- Edges: m × n
Cycle Graph (Cₙ)
Single cycle of n vertices.
- Edges: n
- Each vertex has degree 2
Path Graph (Pₙ)
Single path of n vertices.
- Edges: n-1
- Two vertices have degree 1, rest have degree 2
Hypercube (Qₙ)
Vertices are n-bit binary strings; edges connect strings differing by one bit.
- Vertices: 2ⁿ
- Edges: n × 2ⁿ⁻¹
Q₃ (3-cube):
011 -------- 111
/| /|
010 -------- 110
| | | |
| 001 ------|-101
|/ |/
000 -------- 100
7. Traversals Preview
Two fundamental ways to explore a graph:
Breadth-First Search (BFS)
Explore all neighbors first, then neighbors' neighbors.
- Uses a queue
- Finds shortest paths in unweighted graphs
Depth-First Search (DFS)
Explore as far as possible before backtracking.
- Uses a stack (or recursion)
- Useful for topological sort, cycle detection
Detailed coverage in the Algorithms module.
8. Application to Computer Science
Graph Implementation in Python
# Adjacency List representation
class Graph:
def __init__(self, directed=False):
self.adj = {} # vertex -> list of neighbors
self.directed = directed
def add_vertex(self, v):
if v not in self.adj:
self.adj[v] = []
def add_edge(self, u, v, weight=None):
self.add_vertex(u)
self.add_vertex(v)
self.adj[u].append(v if weight is None else (v, weight))
if not self.directed:
self.adj[v].append(u if weight is None else (u, weight))
def neighbors(self, v):
return self.adj.get(v, [])
def vertices(self):
return list(self.adj.keys())
def degree(self, v):
return len(self.adj.get(v, []))
# Example usage
g = Graph()
g.add_edge('A', 'B')
g.add_edge('A', 'C')
g.add_edge('B', 'D')
g.add_edge('C', 'D')
print(g.neighbors('A')) # ['B', 'C']
print(g.degree('A')) # 2
Adjacency Matrix Implementation
import numpy as np
class GraphMatrix:
def __init__(self, vertices):
self.vertices = vertices
self.v_index = {v: i for i, v in enumerate(vertices)}
n = len(vertices)
self.matrix = np.zeros((n, n), dtype=int)
def add_edge(self, u, v, weight=1):
i, j = self.v_index[u], self.v_index[v]
self.matrix[i][j] = weight
self.matrix[j][i] = weight # Remove for directed
def has_edge(self, u, v):
i, j = self.v_index[u], self.v_index[v]
return self.matrix[i][j] != 0
def neighbors(self, v):
i = self.v_index[v]
return [self.vertices[j] for j in range(len(self.vertices))
if self.matrix[i][j] != 0]
# Example
g = GraphMatrix(['A', 'B', 'C', 'D'])
g.add_edge('A', 'B')
g.add_edge('A', 'C')
print(g.matrix)
print(g.has_edge('A', 'B')) # True
print(g.has_edge('A', 'D')) # False
Real-World Applications
# Social Network (undirected)
social = Graph()
social.add_edge('Alice', 'Bob') # Friends
social.add_edge('Bob', 'Charlie')
# Who are Alice's friends-of-friends?
# Web Pages (directed)
web = Graph(directed=True)
web.add_edge('PageA', 'PageB') # PageA links to PageB
# Used by PageRank algorithm
# Road Network (weighted)
roads = Graph()
roads.add_edge('Home', 'Work', 15) # 15 minutes
roads.add_edge('Home', 'Store', 8)
roads.add_edge('Store', 'Work', 10)
# Find shortest path
# Dependency Graph (directed)
deps = Graph(directed=True)
deps.add_edge('main.c', 'utils.h') # main.c depends on utils.h
deps.add_edge('main.c', 'config.h')
# Topological sort gives build order
Detecting Properties
def is_bipartite(graph):
"""Check if graph can be 2-colored"""
color = {}
for start in graph.vertices():
if start in color:
continue
# BFS to color components
queue = [start]
color[start] = 0
while queue:
v = queue.pop(0)
for neighbor in graph.neighbors(v):
if neighbor not in color:
color[neighbor] = 1 - color[v]
queue.append(neighbor)
elif color[neighbor] == color[v]:
return False
return True
def has_cycle(graph):
"""Check for cycle using DFS"""
visited = set()
rec_stack = set() # Currently in recursion stack
def dfs(v, parent=None):
visited.add(v)
rec_stack.add(v)
for neighbor in graph.neighbors(v):
if neighbor not in visited:
if dfs(neighbor, v):
return True
elif neighbor in rec_stack and neighbor != parent:
return True
rec_stack.remove(v)
return False
for v in graph.vertices():
if v not in visited:
if dfs(v):
return True
return False
9. Euler and Hamilton Paths
Eulerian Paths and Circuits
Eulerian Path: Uses every edge exactly once Eulerian Circuit: Eulerian path that starts and ends at same vertex
Conditions:
- Circuit exists iff all vertices have even degree
- Path exists iff exactly 0 or 2 vertices have odd degree
Hamiltonian Paths and Circuits
Hamiltonian Path: Visits every vertex exactly once Hamiltonian Circuit: Hamiltonian path returning to start
Finding Hamiltonian paths is NP-complete (no efficient algorithm known).
Exercises
Basic
For the following graph, find:
- Number of vertices and edges
- Degree of each vertex
- All paths from A to D
A --- B --- E | | C --- DDraw the adjacency matrix and adjacency list for:
1 → 2 → 3 ↓ ↑ 4 ------Is this graph bipartite? Why or why not?
A --- B | / | | / | C --- D
Intermediate
Prove that a tree with n vertices has exactly n-1 edges.
How many edges does Kₙ (complete graph on n vertices) have?
A graph has vertices with degrees 1, 2, 2, 3, 3, 3. How many edges does it have?
Advanced
Prove: A connected graph has an Eulerian circuit iff every vertex has even degree.
Find the number of spanning trees in K₄.
Implement a function to find all connected components of a graph.
Summary
- Graphs consist of vertices and edges
- Types: directed/undirected, weighted/unweighted, connected/disconnected
- Representations: adjacency matrix (O(V²)), adjacency list (O(V+E))
- Handshaking lemma: sum of degrees = 2 × edges
- Trees: connected graphs with no cycles
- Bipartite: no odd cycles, 2-colorable