Graph Theory - Types, Degree Theorems, Special Graphs, Coloring, BFS & DFS
Data Structure Module — The mathematics of relationships
| # | Topic | Why It Matters |
|---|---|---|
| 1 | Graph definition & terminology | Foundation of all graph problems |
| 2 | Directed vs Undirected graphs | In-degree, out-degree, digraphs |
| 3 | Degree theorems | Handshake lemma — exam favourite |
| 4 | Special graphs | Complete, Regular, Cycle, Wheel, N-Cube, Bipartite |
| 5 | Walk, Path, Cycle | Precise definitions that exams test |
| 6 | Graph coloring | Chromatic number — deep equivalence results |
| 7 | Representations | Adjacency list & matrix |
| 8 | BFS & DFS | Traversal algorithms |
A graph G = (V, E) where:
Real-world examples:
Cities ←→ Roads (undirected, weighted)
People ←→ Friendships (undirected)
Web pages ←→ Hyperlinks (directed)
States ←→ Transitions (directed)
Example Graph:
A ─── B
│ │
│ │
C ─── D ─── E
V = {A, B, C, D, E}
E = {(A,B), (A,C), (B,D), (C,D), (D,E)}
|V| = 5, |E| = 5
Graph theory is mathematics studying relationships. Every social network, neural network, compiler dependency, and internet routing table is a graph.
Undirected Graph: Directed Graph (Digraph):
A ─── B A ───→ B
│ │ ↑ │
│ │ │ ↓
C ─── D C ←─── D
Edge (u,v) = Edge (v,u) Edge (u,v) ≠ Edge (v,u)
No direction u → v is one-way
Degree of a vertex = number of edges connected to it
A ─── B ─── E
│ │
C ─── D
deg(A) = 2 (edges to B, C)
deg(B) = 3 (edges to A, D, E)
deg(C) = 2 (edges to A, D)
deg(D) = 2 (edges to B, C)
deg(E) = 1 (edge to B)
In-degree = number of INCOMING edges
Out-degree = number of OUTGOING edges
A ───→ B
↑ │
│ ↓
C ←─── D
Vertex │ In-degree │ Out-degree
───────┼───────────┼───────────
A │ 1 │ 1 (C→A in, A→B out)
B │ 1 │ 1 (A→B in, B→D out)
C │ 1 │ 1 (D→C in, C→A out)
D │ 1 │ 1 (B→D in, D→C out)
Key theorem: Sum of in-degrees = Sum of out-degrees = |E| (number of edges)
┌────────────────────────────────────────────────┐
│ Sum of degrees of ALL vertices = 2 × |E| │
│ │
│ Σ deg(v) = 2|E| │
│ │
│ WHY? Every edge contributes 2 to total │
│ degree (one for each endpoint). │
└────────────────────────────────────────────────┘
Example:
A ─── B ─── E |E| = 5
│ │
C ─── D
deg(A) + deg(B) + deg(C) + deg(D) + deg(E)
= 2 + 3 + 2 + 2 + 1
= 10
= 2 × 5 ✓
┌──────────────────────────────────────────────────┐
│ The number of ODD-degree vertices is │
│ ALWAYS EVEN. │
│ │
│ (Because 2E is even, and sum of even-degree │
│ vertices is even, so sum of odd-degree │
│ vertices must also be even.) │
└──────────────────────────────────────────────────┘
This means:
✗ Impossible: graph with exactly 1 odd-degree vertex
✗ Impossible: graph with exactly 3 odd-degree vertices
✓ Possible: graph with 0, 2, 4, 6... odd-degree vertices
Σ in-degree = Σ out-degree = |E|
Every directed edge contributes:
+1 to out-degree of source
+1 to in-degree of destination
No self-loops, no parallel edges (multiple edges between same pair).
Parallel edges allowed, but no self-loops.
Both self-loops and parallel edges allowed.
Simple: Multigraph: Pseudograph:
A ─── B A ═══ B A ═══ B
│ │ │ │ ╭─╮
C ─── D C C ╰─╯ ← self-loop
No loops, Parallel edges Loops AND
no parallels allowed parallels allowed
Exam detail: A self-loop contributes 2 to the degree of that vertex (not 1!).
Only isolated vertices, no edges.
A B C D
|V| = 4, |E| = 0
Every vertex has degree 0.
Every vertex connected to every other vertex.
K₃: K₄: K₅:
A A A
/ \\ / │ \\ / │ X │ \\
B───C B──┼──C B──┼─X─┼──C
│ │ │ │ │ X │ │
└──D──┘ D──┼───┼──E
\\ │ │ /
\\│ │/
┌─────────────────────────────────────────────┐
│ Number of edges = n(n − 1) / 2 │
│ Degree of each vertex = n − 1 │
│ │
│ K₃: edges = 3(2)/2 = 3 │
│ K₄: edges = 4(3)/2 = 6 │
│ K₅: edges = 5(4)/2 = 10 │
└─────────────────────────────────────────────┘
All vertices have the same degree r.
r-regular graph on n vertices:
┌────────────────────────────────────────────┐
│ Number of edges = (n × r) / 2 │
│ │
│ Constraint: n × r must be EVEN │
│ (because edges are whole numbers) │
└────────────────────────────────────────────┘
Examples:
• 0-regular: isolated vertices (null graph)
• 1-regular: perfect matching
• 2-regular: disjoint union of cycles
• (n-1)-regular on n vertices: complete graph Kₙ
3-regular graph on 4 vertices:
edges = (4 × 3) / 2 = 6 = K₄ (complete graph!)
Each vertex has degree 2. Looks like a polygon.
C₃: C₄: C₅: C₆:
A A───B A───B A───B
/ \\ │ │ / │ \\ │ │
B───C D───C E │ C F C
\\ │ / │ │
D───┘ E───D
Each vertex: degree = 2
Edges = n (same as vertices)
Cₙ is 2-regular
CHROMATIC NUMBER:
┌───────────────────────────────────┐
│ χ(Cₙ) = 2 if n is EVEN │
│ χ(Cₙ) = 3 if n is ODD │
│ │
│ Odd cycle breaks 2-coloring! │
└───────────────────────────────────┘
Take Cₙ₋₁ + add a center vertex connected to all outer vertices.
W₄ (C₃ + center): W₅ (C₄ + center):
A A───B
/│\\ / │╲ │
/ │ \\ / │ ╲│
B──D──C E───D───C
hub hub = D
Center vertex: degree = n − 1
Outer vertices: degree = 3
Edges = 2(n − 1)
Vertices = binary strings of length n. Two vertices connected if they differ in exactly one bit.
Q₁: 0 ─── 1 (2 vertices, 1 edge)
Q₂: 00 ── 01 (4 vertices, 4 edges)
│ │
10 ── 11
Q₃: 000──001 (8 vertices, 12 edges)
│╲ │╲
010──011 │
│ 100──101
│╱ │╱
110──111
┌──────────────────────────────────────┐
│ Qₙ has: │
│ • 2ⁿ vertices │
│ • n × 2⁽ⁿ⁻¹⁾ edges │
│ • Each vertex has degree = n │
│ (Qₙ is n-regular!) │
└──────────────────────────────────────┘
Q₃: 2³ = 8 vertices, 3 × 2² = 12 edges, degree = 3
Vertices divided into two disjoint sets V₁ and V₂. Edges only go between sets (never within a set).
Bipartite: NOT Bipartite:
V₁ = {A, B} A ─── B
V₂ = {C, D, E} │ │
C ────┘
A ─── C (triangle = odd cycle!)
A ─── D
B ─── D
B ─── E
┌─────────────────────────────────────────────┐
│ Key property: No ODD-LENGTH cycles! │
│ │
│ A graph is bipartite ⟺ it has no odd │
│ cycles (this is a theorem!) │
│ │
│ Chromatic number: χ = 2 │
│ (if graph has at least one edge) │
└─────────────────────────────────────────────┘
Every vertex in V₁ connects to every vertex in V₂.
K₂,₃:
V₁: A ──╲──╲── C
╲ ╲ ╲
V₂: D E F
A connects to D, E, F
B connects to D, E, F
┌──────────────────────────────────────┐
│ Number of edges = m × n │
│ │
│ K₂,₃: edges = 2 × 3 = 6 │
│ K₃,₃: edges = 3 × 3 = 9 │
│ K₁,ₙ: edges = n (star graph!) │
└──────────────────────────────────────┘
These have precise definitions. Exams trap people here!
┌────────────┬──────────────────┬──────────────────┐
│ Term │ Vertices repeat? │ Edges repeat? │
├────────────┼──────────────────┼──────────────────┤
│ Walk │ YES │ YES │
│ Trail │ YES │ NO │
│ Path │ NO │ NO │
│ Cycle │ Closed path │ NO │
└────────────┴──────────────────┴──────────────────┘
Example graph:
A ─── B ─── C
│ │
D ─── E ─── F
Walk: A → B → C → B → A (vertices & edges repeat)
Trail: A → B → C → F → E → D → A (no edge repeats)
Path: A → B → C → F (no vertex repeats)
Cycle: A → B → C → F → E → D → A (closed, no vertex repeats except start=end)
H is a subgraph of G if H's vertices and edges are subsets of G's.
G: H (subgraph of G):
A ─── B A ─── B
│ │ │
C ─── D C
V(H) ⊆ V(G) and E(H) ⊆ E(G)
Spanning subgraph: includes ALL vertices of G.
(edges may be a subset)
Two graphs are isomorphic if there exists a bijection between vertices that preserves adjacency.
Graph 1: Graph 2:
A ─── B 1 ─── 2
│ │ │ │
C ─── D 3 ─── 4
Mapping: A↔1, B↔2, C↔3, D↔4
Same structure, different labels = ISOMORPHIC
"Twins wearing different clothes"
Quick checks (necessary but NOT sufficient):
• Same number of vertices
• Same number of edges
• Same degree sequence
A vertex whose removal disconnects the graph.
A ─── B ─── C
│
D ─── E
Remove B: A is disconnected from {C, D, E}
→ B is a CUT VERTEX (articulation point)
Remove D: {A, B, C} disconnected from E
→ D is also a cut vertex
Remove A: graph stays connected
→ A is NOT a cut vertex
Cut vertices are critical in connectivity analysis — removing them breaks the network.
Proper coloring: Adjacent vertices must have different colors.
Chromatic number χ(G): Minimum number of colors needed.
Example:
A ─── B Color assignment:
│ │ A = Red
C ─── D B = Blue
C = Blue
A-B adjacent → different colors ✓ D = Red
A-C adjacent → different colors ✓
B-D adjacent → different colors ✓ χ(G) = 2 (two colors suffice)
C-D adjacent → different colors ✓
┌───────────────────────────────────────────────┐
│ Graph │ χ (Chromatic Number) │
├─────────────────────┼─────────────────────────┤
│ Null graph │ 1 │
│ Tree (any tree) │ 2 │
│ Bipartite graph │ 2 │
│ Complete graph Kₙ │ n │
│ Cycle Cₙ (even n) │ 2 │
│ Cycle Cₙ (odd n) │ 3 │
│ Wheel Wₙ │ 3 (even n) or 4 (odd n)│
└───────────────────────────────────────────────┘
┌──────────────────────────────────────────────────┐
│ THEOREM: A graph is 2-chromatic (χ = 2) │
│ if and only if it is BIPARTITE. │
│ │
│ 2-colorable ⟺ bipartite ⟺ no odd cycles │
│ │
│ This links coloring, structure, and cycles │
│ into one beautiful equivalence. │
└──────────────────────────────────────────────────┘
# Using dictionary
graph = {
'A': ['B', 'C'], # A connects to B and C
'B': ['A', 'D'], # B connects to A and D
'C': ['A', 'D'],
'D': ['B', 'C', 'E'],
'E': ['D']
}
# Check neighbors
print(graph['A']) # ['B', 'C']
# Check edge exists
print('B' in graph['A']) # True — O(degree)
# For nodes A=0, B=1, C=2, D=3, E=4
matrix = [
[0, 1, 1, 0, 0], # A: connects to B, C
[1, 0, 0, 1, 0], # B: connects to A, D
[1, 0, 0, 1, 0], # C: connects to A, D
[0, 1, 1, 0, 1], # D: connects to B, C, E
[0, 0, 0, 1, 0] # E: connects to D
]
# Check edge A-B exists
print(matrix[0][1] == 1) # True — O(1)
| Feature | Adjacency List | Adjacency Matrix |
|---|---|---|
| Space | O(V + E) | O(V²) |
| Edge check | O(degree) | O(1) |
| Add edge | O(1) | O(1) |
| Best for | Sparse graphs | Dense graphs |
Uses a Queue (FIFO).
from collections import deque
def bfs(graph, start):
visited = set()
queue = deque([start])
visited.add(start)
while queue:
node = queue.popleft() # Remove from front
print(node, end=" ")
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
# Output: A B C D E (level by level)
Uses a Stack (or recursion).
def dfs(graph, node, visited=None):
if visited is None:
visited = set()
visited.add(node)
print(node, end=" ")
for neighbor in graph[node]:
if neighbor not in visited:
dfs(graph, neighbor, visited)
# Output: A B D C E (goes deep first)
| Feature | BFS | DFS |
|---|---|---|
| Data structure | Queue | Stack / Recursion |
| Explores | Level by level | Deep first |
| Shortest path (unweighted) | Yes | No |
| Memory | More | Less |
| Time complexity | O(V + E) | O(V + E) |
| Use case | Nearest, shortest | All paths, cycles |
| Formula / Fact | Value |
|---|---|
| Handshake lemma | Σ deg(v) = 2 |
| Directed graph | Σ in-deg = Σ out-deg = |
| Odd-degree vertices | Count is always EVEN |
| Kₙ edges | n(n−1)/2 |
| Regular graph edges | (n × r) / 2 |
| Kₘ,ₙ edges | m × n |
| Qₙ vertices | 2ⁿ |
| Qₙ edges | n × 2⁽ⁿ⁻¹⁾ |
| Self-loop | Contributes 2 to degree |
| Bipartite ⟺ | No odd cycles ⟺ χ = 2 |
One-liner for each concept:
| Concept | Key Takeaway |
|---|---|
| Graph G=(V,E) | Vertices + Edges. Directed or Undirected. |
| Handshake Lemma | Sum of all degrees = 2 × edges. Odd-degree vertices count is ALWAYS even. |
| Complete Kₙ | Every pair connected. Edges = n(n−1)/2. Degree = n−1. |
| Regular Graph | All vertices same degree r. Edges = nr/2. |
| Bipartite | Two sets, edges only between sets. No odd cycles. χ = 2. |
| Cycle Cₙ | χ = 2 (even n), χ = 3 (odd n). Polygon shape. |
| N-Cube Qₙ | 2ⁿ vertices, n·2⁽ⁿ⁻¹⁾ edges, n-regular. |
| Cut Vertex | Removing it disconnects the graph. Articulation point. |
| Chromatic Number | Min colors for proper coloring. Tree=2, Kₙ=n. |
| BFS | Queue. Level-by-level. Shortest path in unweighted graphs. |
| DFS | Stack/recursion. Go deep. Cycle detection, all paths. |
The Golden Rules:
Video Courses:
Articles & Visualizations:
Practice Problems:
Test your understanding with step-by-step solutions
10 questions · 90s per question
Each question has a 90-second time limit. Unanswered questions will be auto-submitted when time runs out.