Graph Terminology & Handshaking Lemma
A graph $G = (V, E)$ consists of vertices $V$ connected by edges $E$. The degree $\deg(v)$ is the number of edges incident to $v$ (loops count twice).
Types of graphs: Simple (no loops or multiple edges), Complete $K_n$ (every pair connected, $\binom{n}{2}$ edges), Bipartite $K_{m,n}$ (vertices partitioned into two sets).
Adjacency Matrices & Counting Walks
The adjacency matrix $\mathbf{A}$ has $A_{ij} = 1$ if an edge connects $v_i$ to $v_j$ (and $0$ otherwise):
A walk can revisit vertices and edges; a path cannot repeat vertices; a trail cannot repeat edges.
Eulerian Trails vs. Hamiltonian Cycles
- Eulerian Trail / Circuit (Edge traversal):
- Eulerian Circuit: Traverses every edge exactly once and returns to the start $\iff$ graph is connected and all vertices have even degree.
- Eulerian Trail: Traverses every edge exactly once $\iff$ graph is connected and exactly two vertices have odd degree (starts at one odd, ends at the other).
- Hamiltonian Path / Cycle (Vertex traversal):
- Visits every vertex exactly once (cycle returns to start).
- No simple degree parity rule exists (NP-hard problem).
Travelling Salesperson Problem (TSP) Bounds
Finding the Hamiltonian cycle of minimum total weight in a complete weighted network:
Minimum Spanning Trees: Kruskal vs. Prim
A spanning tree connects all $n$ vertices using $n - 1$ edges with no cycles:
- Kruskal's Algorithm: Sort all edges by ascending weight. Greedily add the cheapest edge that does not form a cycle, until $n - 1$ edges are selected.
- Prim's Algorithm: Start from a single vertex. At each step, add the cheapest edge connecting an already included vertex to an unvisited vertex.
A graph has 7 vertices with degrees $4, 3, 2, 3, 2, 4, x$. Find the value of $x$ if the graph contains 11 edges.
Solution:
By the Handshaking Lemma: $\sum \deg(v) = 2|E| = 2(11) = 22$. [M1]
$4 + 3 + 2 + 3 + 2 + 4 + x = 22 \implies 18 + x = 22$. [M1]
$x = 4$. [A1]
Determine whether a simple graph with 5 vertices of degrees $3, 3, 3, 2, 1$ can exist. Justify your answer by giving its edges or explaining a contradiction.
Solution:
Sum of degrees $= 3 + 3 + 3 + 2 + 1 = 12$. [M1]
Four vertices have odd degree, so the parity condition is satisfied. This necessary condition alone does not prove existence. [R1]
A construction proves existence: label the vertices $A,B,C,D,E$ and use edges $AB,AC,AD,BC,BE,CD$. Their degrees are respectively $3,3,3,2,1$; there are no loops or repeated edges. Thus the requested simple graph exists. [A1]
The adjacency matrix of a graph with vertices $A, B, C, D$ is:
$$\mathbf{A} = \begin{pmatrix} 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 \end{pmatrix}$$Find the number of walks of length 3 between vertex $A$ and vertex $D$ by calculating $\mathbf{A}^3$.
Solution:
Compute $\mathbf{A}^2$: row 1 times cols gives $[2, 1, 1, 2]$ for row 1. [M1]
To find the $(1, 4)$ entry of $\mathbf{A}^3$, compute (row 1 of $\mathbf{A}^2$) $\cdot$ (col 4 of $\mathbf{A}$): [M1]
Row 1 of $\mathbf{A}^2 = [2, 1, 1, 2]$. Col 4 of $\mathbf{A} = [0, 1, 1, 0]^T$. [M1]
$(1, 4)$ entry $= 2(0) + 1(1) + 1(1) + 2(0) = 2$. [A1]
There are 2 distinct walks of length 3 between $A$ and $D$.
A connected graph has vertices with degrees: $A: 4, B: 3, C: 4, D: 3, E: 2$. State whether the graph contains an Eulerian circuit, an Eulerian trail, or neither, and identify the starting vertex of any valid trail.
Solution:
Vertices $B$ and $D$ have odd degree (3); all other vertices have even degrees ($4, 4, 2$). [A1]
Since exactly two vertices have odd degree, the graph contains an **Eulerian trail** (not an Eulerian circuit). [A1]
Any Eulerian trail must start at either $B$ or $D$ (and end at the other odd vertex). [R1]
A complete weighted graph $K_4$ on vertices $A, B, C, D$ has edge weights: $AB = 8, AC = 12, AD = 15, BC = 9, BD = 11, CD = 7$.
- Use the Nearest Neighbour Algorithm starting at vertex $A$ to find an upper bound for the Travelling Salesperson Problem.
- State the tour and its total weight.
Solution:
Start at $A$: from $A$, available edges are $AB(8), AC(12), AD(15)$. Cheapest is $B$ (weight 8). [M1]
From $B$: unvisited vertices are $C$ and $D$. $BC = 9, BD = 11$. Cheapest is $C$ (weight 9). [M1]
From $C$: only unvisited vertex is $D$. Edge $CD = 7$. [M1]
From $D$: return to start $A$. Edge $DA = 15$. [M1]
Tour: $A \to B \to C \to D \to A$. Total weight $= 8 + 9 + 7 + 15 = 39$. [A1]
For the network in Exercise 5, use the deleted vertex method deleting vertex $A$ to determine a lower bound for the TSP.
Solution:
Delete vertex $A$. The remaining subgraph has vertices $\{B, C, D\}$ with edge weights $BC = 9, BD = 11, CD = 7$. [M1]
Find the MST of $\{B, C, D\}$: select cheapest edge $CD(7)$, then next cheapest connecting edge $BC(9)$. MST weight $= 7 + 9 = 16$. [M1][A1]
Find the two shortest edges incident to the deleted vertex $A$: $AB = 8$ and $AC = 12$. [M1]
Lower Bound $= \text{Weight of MST} + \text{Two shortest edges to } A = 16 + 8 + 12 = 36$. [A1]
Use Kruskal's algorithm on the 5-vertex graph with edges: $AB = 4, BC = 3, CD = 6, DE = 2, EA = 7, AC = 5, BE = 8, BD = 4$. List the edges selected in order and state the total weight of the MST.
Solution:
Sort edges by weight: $DE(2), BC(3), AB(4), BD(4), AC(5), CD(6), EA(7), BE(8)$. [M1]
1. Add $DE(2)$ [Edges: 1]
2. Add $BC(3)$ [Edges: 2]
3. Add $AB(4)$ [Edges: 3]
4. Add $BD(4)$ [Edges: 4, connects all 5 vertices without forming cycles]. [A2]
Total MST weight $= 2 + 3 + 4 + 4 = 13$. [A1]
Apply Prim's algorithm starting at vertex $A$ to the same network in Exercise 7, showing the edges chosen at each stage.
Solution:
Start at $\{A\}$: edges incident to $A$ are $AB(4), AC(5), AE(7)$. Cheapest is $AB(4)$. Add $B$. Connected set: $\{A, B\}$. [M1]
From $\{A, B\}$: available edges are $BC(3), BD(4), AC(5), BE(8), AE(7)$. Cheapest is $BC(3)$. Add $C$. Connected set: $\{A, B, C\}$. [M1]
From $\{A, B, C\}$: available edges to unvisited $\{D, E\}$ are $BD(4), CD(6), AE(7), BE(8)$. Cheapest is $BD(4)$. Add $D$. Connected set: $\{A, B, C, D\}$. [M1]
From $\{A, B, C, D\}$ to $\{E\}$: cheapest is $DE(2)$. Add $E$. [A1]
MST Edges: $AB, BC, BD, DE$. Total weight $= 4 + 3 + 4 + 2 = 13$ (Identical to Kruskal's!).
State how many edges exist in the complete graph $K_n$, and calculate the number of edges in $K_8$.
Solution:
Formula for complete graph: $|E| = \binom{n}{2} = \frac{n(n - 1)}{2}$. [M1]
For $n = 8$: $|E| = \frac{8(7)}{2} = \frac{56}{2} = 28$ edges. [A2]
Describe the Chinese Postman Problem, and explain how it is solved when a graph contains 4 vertices of odd degree.
Solution:
The Chinese Postman Problem seeks a closed walk of minimum weight that traverses every edge at least once. [A1]
If 4 vertices have odd degree ($A, B, C, D$), they must be paired up into two disjoint pairs in all 3 possible combinations: $(AB, CD)$, $(AC, BD)$, $(AD, BC)$. [M1]
Calculate the shortest path between the paired vertices for each combination, and find the combination with the minimum sum. [M1]
Duplicate these shortest paths; the resulting multigraph has all even degrees and contains an Eulerian circuit with optimal weight $= \text{Total edge weight} + \text{weight of duplicated paths}$. [A1]
Core Formulas (Topic 3 AHL)
| Handshaking Lemma | $$\sum_{v \in V} \deg(v) = 2|E|$$ |
| Walks of Length $k$ | $$(\mathbf{A}^k)_{ij} = \text{number of walks from } v_i \text{ to } v_j$$ |
| Spanning Tree Edge Count | $$|E| = |V| - 1 = n - 1$$ |
| Complete Graph Edges | $$\binom{n}{2} = \frac{n(n-1)}{2}$$ |
Top 5 IB Exam Traps to Avoid
- Trap 1: Confusing Eulerian (edges) with Hamiltonian (vertices): Eulerian travels every *edge*; Hamiltonian visits every *vertex*.
- Trap 2: Forgetting to return to start in TSP Nearest Neighbour: An upper bound tour must return to the initial starting vertex! Forgetting the closing edge invalidates the tour.
- Trap 3: Cycle formation in Kruskal's algorithm: You must reject an edge if both endpoints are already connected in the current forest.
- Trap 4: Lower Bound Deleted Vertex selection: You must add the *two shortest* edges incident to the deleted vertex, not just one.
- Trap 5: Counting loops in vertex degree: Each loop contributes 2 to the degree of its vertex (one out, one in).
5-Question Concept Check
Score: - / 51. A connected graph contains an Eulerian circuit if and only if:
2. How many edges does a spanning tree on 12 vertices contain?
3. What does entry $(i, j)$ in matrix $\mathbf{A}^4$ represent?
4. Which algorithm finds an UPPER BOUND for the Travelling Salesperson Problem?
5. A graph has 6 vertices with degrees $3, 3, 2, 2, 1, 1$. How many edges does the graph have?