Further Number & Graph Theory — IB Math AI (HL)

1. Introduction to Graph Theory

Graph theory is the study of graphs — mathematical structures used to model pairwise relations between objects. A graph $G = (V, E)$ consists of a set of vertices (nodes) $V$ and a set of edges $E$ connecting pairs of vertices.

Key Terminology

Term	Definition	Example
Vertex (node)	A point in the graph	City in a road network
Edge (arc)	A connection between two vertices	Road between two cities
Degree of a vertex	Number of edges incident to it	$\deg(v) = 3$ means 3 edges meet at $v$
Simple graph	No loops, no multiple edges	Standard undirected graph
Multigraph	Multiple edges allowed between vertices	Two roads between same cities
Directed graph (digraph)	Edges have direction (arrows)	One-way streets
Weighted graph	Each edge has a numerical weight	Road network with distances

Handshaking Lemma

For any graph $G$, the sum of all vertex degrees equals twice the number of edges:

$$\sum_{v \in V} \deg(v) = 2|E|$$

Consequence: The number of vertices with odd degree is always even.

Types of Graphs

Complete graph $K_n$: every pair of vertices is connected. Has $\frac{n(n-1)}{2}$ edges.
Bipartite graph: vertices split into two disjoint sets $A, B$; edges only go between $A$ and $B$.
Connected graph: there is a path between every pair of vertices.
Tree: connected graph with no cycles; a tree with $n$ vertices has exactly $n-1$ edges.
Subgraph: a graph formed from a subset of vertices and edges of a larger graph.

2. Adjacency Matrices

An adjacency matrix $A$ is an $n \times n$ matrix where $a_{ij}$ represents the number of edges from vertex $i$ to vertex $j$.

Adjacency Matrix Properties

For an undirected graph: $A$ is symmetric ($a_{ij} = a_{ji}$)
For a simple graph: all diagonal entries $a_{ii} = 0$ (no self-loops)
The $(i,j)$ entry of $A^2$ gives the number of walks of length 2 from vertex $i$ to vertex $j$
More generally, $(A^k)_{ij}$ = number of walks of length $k$ from $i$ to $j$
The degree of vertex $i$ = row sum (or column sum for undirected) of row $i$

Worked Example 1

Constructing an Adjacency Matrix

A graph has vertices $A, B, C, D$ with edges: $AB$, $AC$, $BC$, $BD$, $CD$. Construct the adjacency matrix and find the number of walks of length 2 from $A$ to $D$.

Label rows and columns with vertices $A, B, C, D$. Enter 1 if an edge exists, 0 otherwise. $$A = \begin{pmatrix} 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 \end{pmatrix}$$

Verify degrees using row sums: $\deg(A)=2$, $\deg(B)=3$, $\deg(C)=3$, $\deg(D)=2$. Check: $2+3+3+2=10=2\times 5$ edges. ✓

Compute $A^2$ to find walks of length 2. The $(1,4)$ entry of $A^2$ (row $A$, column $D$): $$[A^2]_{AD} = (0)(0)+(1)(1)+(1)(1)+(0)(0) = 0+1+1+0 = 2$$ So there are 2 walks of length 2 from $A$ to $D$: $A \to B \to D$ and $A \to C \to D$.

3. Minimum Spanning Trees

A spanning tree of a connected graph is a subgraph that is a tree containing all $n$ vertices (and exactly $n-1$ edges). A minimum spanning tree (MST) is a spanning tree with the smallest possible total edge weight.

Why MSTs matter: MSTs solve real-world problems like designing the cheapest road/cable network connecting all cities, or minimising pipeline length in an oil field.

Kruskal's Algorithm

Sort all edges by weight (ascending). Add edges one by one, skipping any edge that would create a cycle. Stop when $n-1$ edges have been added.

Kruskal's Algorithm — Steps

List all edges in non-decreasing order of weight
Pick the lightest edge. Add it to the MST if it does not form a cycle
Repeat step 2 until $n-1$ edges have been selected
If an edge would connect two vertices already in the same connected component, reject it (cycle detection)

Time complexity: $O(E \log E)$ for sorting.

Prim's Algorithm

Start from any vertex. Greedily add the cheapest edge connecting a vertex in the current tree to a vertex not yet in the tree. Repeat until all vertices are included.

Prim's Algorithm — Steps

Choose any starting vertex; mark it as part of the MST
Find the minimum-weight edge connecting any MST vertex to any non-MST vertex
Add that edge and the new vertex to the MST
Repeat steps 2–3 until all vertices are in the MST

Key difference from Kruskal: Prim's grows a single connected component; Kruskal's may add isolated edges that eventually merge.

Worked Example 2

Applying Kruskal's Algorithm

A weighted graph has 5 vertices $\{A,B,C,D,E\}$ with edges and weights: $AB=3$, $AC=5$, $BC=2$, $BD=6$, $BE=4$, $CD=1$, $CE=7$, $DE=5$. Find the MST using Kruskal's algorithm.

Sort edges by weight: $CD=1$, $BC=2$, $AB=3$, $BE=4$, $AC=5$, $DE=5$, $BD=6$, $CE=7$

Add $CD=1$: no cycle. MST = $\{CD\}$. Components: $\{A\},\{B\},\{C,D\},\{E\}$

Add $BC=2$: no cycle. MST = $\{CD, BC\}$. Components: $\{A\},\{B,C,D\},\{E\}$

Add $AB=3$: no cycle. MST = $\{CD, BC, AB\}$. Components: $\{A,B,C,D\},\{E\}$

Add $BE=4$: no cycle — connects $E$ to tree. MST = $\{CD, BC, AB, BE\}$. ✓ $n-1=4$ edges. Stop.

MST total weight: $1+2+3+4 = \mathbf{10}$. The MST uses edges $CD, BC, AB, BE$.

4. Eulerian and Hamiltonian Paths

Eulerian Paths and Circuits

An Eulerian path traverses every edge exactly once. An Eulerian circuit is an Eulerian path that starts and ends at the same vertex.

Euler's Theorems

A connected graph has an Eulerian circuit if and only if every vertex has even degree
A connected graph has an Eulerian path (not a circuit) if and only if it has exactly two vertices of odd degree (the path starts and ends at these vertices)
If there are more than two odd-degree vertices, no Eulerian path exists

Historical context: Euler solved the Königsberg Bridge Problem (1736) — can you cross all 7 bridges of Königsberg exactly once? The answer is no: the graph of bridges has 4 vertices of odd degree. This is considered the birth of graph theory.

Hamiltonian Paths and Circuits

A Hamiltonian path visits every vertex exactly once. A Hamiltonian circuit returns to the starting vertex after visiting every other vertex exactly once.

No simple efficient algorithm exists to determine Hamiltonian circuits — this is an NP-complete problem
For IB purposes: determine by inspection (trial and error for small graphs)
Dirac's theorem: If every vertex in a simple graph with $n \geq 3$ vertices has degree $\geq n/2$, then the graph has a Hamiltonian circuit

Worked Example 3

Determining Eulerian Circuits

A graph has 6 vertices with degrees 2, 3, 4, 3, 2, 4. Does an Eulerian circuit exist? Does an Eulerian path exist?

Count odd-degree vertices: Degrees are 2, 3, 4, 3, 2, 4. There are 2 odd-degree vertices.

Eulerian circuit: Requires ALL vertices to have even degree. Since 2 vertices have odd degree, no Eulerian circuit exists.

Eulerian path: Requires exactly 2 odd-degree vertices. We have exactly 2. So an Eulerian path exists, starting and ending at the two odd-degree vertices.

5. The Chinese Postman Problem

The Chinese Postman Problem (Route Inspection) asks: what is the shortest closed walk that traverses every edge at least once? This models a postman delivering to every street and returning to the depot.

If all vertices have even degree: the graph is Eulerian, and the answer is simply the sum of all edge weights
If there are odd-degree vertices: add the minimum-weight set of extra edges (repeat edges) to make all degrees even, then find the Eulerian circuit
For IB: typically 2 or 4 odd-degree vertices — find minimum-weight matching of odd-degree pairs

Chinese Postman — Algorithm

Find all odd-degree vertices
Find the minimum-weight pairing of these vertices (consider all possible pairings)
Add repeated edges along shortest paths between paired vertices
Total route length = sum of all edges + weight of added repeated edges

6. The Travelling Salesman Problem (TSP)

The Travelling Salesman Problem: find the shortest Hamiltonian circuit in a complete weighted graph (visit every city exactly once and return to start).

The TSP is NP-hard — no known polynomial-time exact algorithm. For IB, we use approximation:

Nearest Neighbour Algorithm (Greedy Heuristic)

Start at any vertex
Move to the nearest unvisited vertex
Repeat until all vertices are visited
Return to the starting vertex

Note: This gives a good approximation but not necessarily the optimal solution. The result depends on the starting vertex chosen.

Lower bound method: Delete one vertex and its edges. Find MST of remaining graph. Add back the two cheapest edges from the deleted vertex. This gives a lower bound for the optimal TSP solution.

Practice Problems

1. A graph has vertices $P, Q, R, S$ with edges $PQ=4$, $PR=7$, $PS=2$, $QR=3$, $QS=6$, $RS=5$. Use Kruskal's algorithm to find the minimum spanning tree and state its total weight.

Show Solution

Sort edges: $PS=2$, $QR=3$, $PQ=4$, $RS=5$, $QS=6$, $PR=7$

Add $PS=2$ ✓, Add $QR=3$ ✓, Add $PQ=4$ ✓ (connects $\{P,S\}$ to $\{Q,R\}$). Now all 4 vertices connected with 3 edges. Stop.

MST edges: $PS, QR, PQ$ | Total weight: $2+3+4 = \mathbf{9}$

2. A connected graph has 8 vertices. Their degrees are: 4, 2, 3, 5, 2, 3, 4, 3. Determine whether an Eulerian circuit exists, and whether an Eulerian path exists.

Show Solution

Odd-degree vertices: 3, 5, 3, 3 — that is 4 vertices with odd degree.

Eulerian circuit: Requires 0 odd-degree vertices. Does NOT exist.

Eulerian path: Requires exactly 2 odd-degree vertices. Does NOT exist (4 odd-degree vertices).

To make an Eulerian circuit, we'd need to add repeated edges to convert all 4 odd-degree vertices to even — this is the Chinese Postman approach.

3. The adjacency matrix of a graph is $A = \begin{pmatrix} 0&1&1&0\\ 1&0&0&1\\ 1&0&0&1\\ 0&1&1&0 \end{pmatrix}$. Find the number of walks of length 2 from vertex 1 to vertex 4, and list all such walks.

Show Solution

$(A^2)_{14}$ = row 1 of $A$ dotted with column 4 of $A$: $(0)(0)+(1)(1)+(1)(1)+(0)(0) = 2$.

Two walks of length 2: $1 \to 2 \to 4$ and $1 \to 3 \to 4$.

Continue Learning

Explore other IB Math AI HL topics

Back to IB Hub Further Statistics →

Further Number & Graph Theory HL

1. Introduction to Graph Theory

Key Terminology

Handshaking Lemma

Types of Graphs

2. Adjacency Matrices

Adjacency Matrix Properties

Constructing an Adjacency Matrix

3. Minimum Spanning Trees

Kruskal's Algorithm

Kruskal's Algorithm — Steps

Prim's Algorithm

Prim's Algorithm — Steps

Applying Kruskal's Algorithm

4. Eulerian and Hamiltonian Paths

Eulerian Paths and Circuits

Euler's Theorems

Hamiltonian Paths and Circuits

Determining Eulerian Circuits

5. The Chinese Postman Problem

Chinese Postman — Algorithm

6. The Travelling Salesman Problem (TSP)

Nearest Neighbour Algorithm (Greedy Heuristic)

Practice Problems

Continue Learning