Menu
EARLY ACCESS JMaths is in active development — new content added regularly

Graph Theory & Algorithms HL

IB Mathematics: Applications & Interpretation · Topic 3: Geometry & Trigonometry
www.jmaths.xyz
1
Vertices, Edges & Degree
A graph consists of vertices (nodes) connected by edges. The degree of a vertex is the number of edges meeting it.
Handshaking lemma
\( \sum deg(v) = 2 \times (number of edges) \)
The sum of all vertex degrees equals twice the number of edges
A B C D E deg(A) = 3 deg(B) = 3 deg(C) = 2 deg(D) = 3 deg(E) = 3 ∑ = 14 = 2×7 7 edges
▶
Key terms: Simple graph = no loops or multiple edges. Connected = path between every pair of vertices. \( K_n \) (complete graph) = every vertex connected to every other.
2
Adjacency Matrices & Walks
The adjacency matrix A is an \( n \times n \) matrix where entry \( a_{ij} \) = number of edges between vertex \( i \) and vertex \( j \).
Number of walks
\( The entry (i, j) of A \)\( k \) gives the number of walks of length \( k \) from vertex \( i \) to vertex \( j \).
Worked Example
Given adjacency matrix A, find the number of walks of length 3 from vertex 1 to vertex 2.
Calculate A3 (use GDC for matrix multiplication)
Read entry (1, 2) of A3
Answer: the value in row 1, column 2 of A3
GDC: Matrix Powers
TI-84 Plus CE
Enter adjacency matrix in [A]: [2ND][MATRIX] → Edit
Calculate: [A]^3 [ENTER] → read entry (1,2)
TI-Nspire CX II
Define: a := [[0,1,1][1,0,1][1,1,0]]
Calculate: a^3 → read entry (1,2)
Casio fx-CG50
Enter matrix in Mat A: [MENU] → Run-Matrix
Calculate: Mat A ^ 3 [EXE] → read entry (1,2)
3
Euler Trails & Circuits
An Euler trail uses every edge exactly once. An Euler circuit is an Euler trail that starts and ends at the same vertex.
Euler circuit exists if:
Every vertex has even degree
(and graph is connected)
Euler trail exists if:
Exactly 2 vertices have odd degree
Trail starts/ends at the odd-degree vertices
Euler circuit: all vertices have even degree 2 2 2 2 → ↓ ← ↑ all even circuit exists 3 2 3 2 2 odd trail only
✗
Common error: Confusing Euler (every \( edge \) once) with Hamilton (every \( vertex \) once). Remember: Euler = Edges.
4
Hamiltonian Paths & Cycles
A Hamiltonian path visits every vertex exactly once. A Hamiltonian cycle visits every vertex exactly once and returns to the start.
▶
No simple test: Unlike Euler, there is no quick rule to determine if a Hamiltonian path/cycle exists. You must search by trial. The IB only tests small graphs where this is feasible.
JMaths · www.jmaths.xyz Graph Theory & Algorithms · Page 1 of 3

Graph Theory & Algorithms HL

IB Mathematics: Applications & Interpretation · Topic 3: Geometry & Trigonometry
www.jmaths.xyz
5
Minimum Spanning Trees (MST)
A spanning tree connects all vertices with no cycles, using \( n - 1 \) edges. The MST has the minimum total weight.
Kruskal’s algorithm
1. List all edges by weight (ascending)
2. Add the cheapest edge that does NOT form a cycle
3. Repeat until \( n - 1 \) edges added
Prim’s algorithm
1. Start at any vertex
2. Add the cheapest edge connecting a visited vertex to an unvisited one
3. Repeat until all vertices included
Worked Example — Kruskal’s
Edges: AB=3, BC=5, AC=7, BD=4, CD=6. Find the MST for vertices A, B, C, D.
Sort: AB=3, BD=4, BC=5, CD=6, AC=7
Add AB=3 (no cycle), BD=4 (no cycle), BC=5 (no cycle). Now 3 edges = \( n-1 = 3 \). Done.
Skip CD=6 (would form cycle B-C-D-B)
Answer: MST = {AB, BD, BC}, total weight = 3 + 4 + 5 = 12
Weighted graph 3 5 4 6 7 A B C D → MST (total = 12) 3 4 5 A B C D
▶
Kruskal vs Prim: Kruskal’s works well with edge lists. Prim’s works well with adjacency matrices (table form). The IB may specify which to use.
6
Travelling Salesman Problem (TSP)
Find the shortest Hamiltonian cycle (visit every vertex exactly once and return). This is NP-hard — we use heuristics for approximation.
Nearest neighbour algorithm (upper bound)
1. Start at a given vertex
2. Move to the nearest unvisited vertex
3. Repeat until all visited, then return to start
Gives an upper bound — a feasible route
Lower bound (deleted vertex)
1. Delete a vertex and all its edges
2. Find MST of remaining graph
3. Add back the two shortest edges to the deleted vertex
Gives a lower bound — optimal \( \geq \) this value
Optimal solution satisfies: lower bound \( \leq \) optimal \( \leq \) upper bound.
✗
Common error: The nearest neighbour does NOT guarantee the optimal route. It is a greedy heuristic. Starting from different vertices may give different (better or worse) results.
7
Chinese Postman Problem
Find the shortest route that traverses every edge at least once and returns to the start. (Think: a postman delivering to every street.)
Algorithm
1. Identify all vertices with odd degree
2. Find the shortest pairings of odd vertices
3. Add these “extra” edges (repeat them) to make all degrees even
4. Total distance = sum of all edges + repeated edges
▶
If all vertices have even degree: the graph already has an Euler circuit. No extra edges needed — total distance = sum of all edge weights.
✗
Common error: With 4 odd vertices (A, B, C, D), there are 3 possible pairings: {AB+CD}, {AC+BD}, {AD+BC}. You must check all three and pick the minimum total. Do not just pick the first pairing.
JMaths · www.jmaths.xyz Graph Theory & Algorithms · Page 2 of 3

Graph Theory & Algorithms HL

IB Mathematics: Applications & Interpretation · Topic 3: Geometry & Trigonometry
www.jmaths.xyz
8
Transition Matrices & Markov Chains
A Markov chain models a system that transitions between states with fixed probabilities. The transition matrix T has columns that sum to 1.
State after \( n \) steps
s\( n \) = T\( n \) s0
s0 = initial state vector (column), T = transition matrix
Steady state
Ts = s
The steady state s satisfies Ts = s, i.e. it is an eigenvector with eigenvalue 1. Components sum to 1.
Worked Example
A brand has two products A and B. Each month, 70% of A users stay with A, 30% switch to B. 40% of B users switch to A, 60% stay. Find the steady state.
T = [0.7 0.4 ; 0.3 0.6]. Solve Ts = s with \( s_1 + s_2 = 1 \).
0.7\( s_1 + 0.4s_2 = s_1 \to -0.3s_1 + 0.4s_2 = 0 \to s_1 = (4/3)s_2 \)
With \( s_1 + s_2 = 1: (4/3)\( s_2 + s_2 = 1 \to s_2 = 3/7, s_1 = 4/7 \)
Answer: Steady state = [4/7 ; 3/7] \( \approx \) [0.571 ; 0.429]
GDC: Markov Chains
TI-84 Plus CE
Enter T in [A], initial state in [B] (as column matrix)
After \( n \) steps: [A]^n \( \times \) [B] [ENTER]
For steady state: compute [A]^100 \( \times \) [B] (converges quickly)
TI-Nspire CX II
Define: t := [[0.7,0.4][0.3,0.6]] and s := [[0.5][0.5]]
After \( n \) steps: \( t^n \times s \)
Steady state: \( t^100 \times s \) or solve the eigenvector equation
Casio fx-CG50
Enter T in Mat A, initial state in Mat B
After \( n \) steps: Mat A ^ n \( \times \) Mat B
Steady state: Mat A ^ 100 \( \times \) Mat B (or use eigenvalue method)
✗
Common error: Columns (not rows) of the transition matrix must sum to 1. If the question gives row probabilities, you may need to transpose. Check the convention used.
✗
Common error: Confusing “after 3 transitions” with “at time 3”. If s0 is the initial state, then after 3 transitions the state is T3s0 (not T2s0).
9
Exam Traps & Key Reminders
✗
Show your working. For algorithms (Kruskal, Prim, nearest neighbour), list each step clearly. The IB awards marks for the process, not just the answer.
▶
TSP bounds: Always state both upper and lower bounds. The optimal solution lies between them. If they are equal, you have found the optimal route.
▶
Quick checks: A tree with \( n \) vertices has exactly \( n - 1 \) edges. A complete graph K\( n \) has \( n(n-1)/2 \) edges. There is always an even number of odd-degree vertices.
▶
Formula booklet: The adjacency matrix, Euler trail/circuit conditions, and Markov chain formula are given. The algorithms (Kruskal, Prim, nearest neighbour, Chinese postman) are NOT in the booklet — learn the steps.
JMaths · www.jmaths.xyz Graph Theory & Algorithms · Page 3 of 3