Welcome to Graph Theory
Welcome to one of the most practical and visual areas of A Level Further Mathematics! Graph theory is the mathematics of connections. Whether you are modelling internet networks, flight routes across Europe, delivery paths, or matching job applicants to roles, graph theory provides the exact mathematical language needed to solve complex real-world problems.
Don't worry if this chapter feels different from standard algebra or calculus. By breaking down the rules, definitions, and algorithms step-by-step, you will quickly master the concepts required for Unit A2 2 Section D: Discrete and Decision Mathematics.
---1. Core Graph Definitions and Classifications
Let's begin by building our graph theory vocabulary from the ground up.
Basic Building Blocks
A graph \(G = (V, E)\) consists of two sets:
• A set of vertices (or nodes), denoted by \(V\). These represent the points or locations.
• A set of edges (or arcs), denoted by \(E\). These represent the links joining pairs of vertices.
A simple graph is a graph with:
• No loops (an edge connecting a vertex to itself).
• No multiple edges (no more than one edge directly connecting the same pair of vertices).
Degree and the Handshaking Lemma
The degree (or valency) of a vertex \(v\), written as \(d(v)\), is the number of edges connected to it.
The Handshaking Lemma:
\(\sum_{v \in V} d(v) = 2|E|\)
Why does this work? Think of a handshake: every single edge has two ends. Whenever you add an edge to a graph, you contribute exactly \(2\) to the total sum of degrees across all vertices.
Crucial Consequence: Because the sum of degrees is always an even number (\(2|E|\)), the number of vertices with an odd degree must always be even. If an exam question asks whether a graph can exist with degree sequence \(3, 3, 3, 2, 2\), the answer is an immediate no, because there are three odd-degree vertices!
Walks, Paths, and Cycles
• A walk is an alternating sequence of vertices and edges.
• A path is a walk in which no vertex is visited more than once.
• A cycle (or circuit) is a closed walk that starts and ends at the exact same vertex, with no other vertices repeated.
Trees and Spanning Trees
A tree is a connected graph that contains no cycles.
For any tree with \(n\) vertices:
• The number of edges is always \(|E| = n - 1\).
A spanning tree of a graph \(G\) is a subgraph that contains all vertices of \(G\) and is a tree. If a connected graph has \(n\) vertices, any spanning tree for that graph must contain exactly \(n - 1\) edges.
Complete Graphs
A complete graph with \(n\) vertices, denoted by \(K_n\), is a simple graph where every single vertex is directly connected to every other vertex by an edge.
The total number of edges in \(K_n\) is given by:
\(|E| = \frac{n(n - 1)}{2}\)
Example: A complete graph with \(5\) vertices, \(K_5\), has \(\frac{5(4)}{2} = 10\) edges.
Planar Graphs and Euler's Formula
A graph is planar if it can be drawn in a single plane (on a flat sheet of paper) such that no edges cross each other.
Euler's Formula for Connected Planar Graphs:
\(V - E + F = 2\)
where:
• \(V\) is the number of vertices,
• \(E\) is the number of edges,
• \(F\) is the number of faces (regions bounded by edges).
Common Examiner Trap: Always remember to count the unbounded exterior face (the open region surrounding the outside of the graph) when calculating \(F\)! For example, a single triangle has \(3\) vertices, \(3\) edges, and \(2\) faces (\(1\) inside region + \(1\) outside region), giving \(3 - 3 + 2 = 2\).
Key Takeaway: Vertices are points, edges are links. The sum of degrees is always \(2|E|\), odd-degree vertices always come in pairs, a tree on \(n\) vertices has \(n - 1\) edges, and planar graphs always satisfy \(V - E + F = 2\).
---2. Bipartite Graphs and Matching Theory
What is a Bipartite Graph?
A bipartite graph is a graph whose vertices can be split into two separate, disjoint sets, \(X\) and \(Y\), such that every edge connects a vertex in set \(X\) to a vertex in set \(Y\). No edges are allowed to connect vertices that are in the same set.
Real-world analogy: Imagine set \(X\) is a group of job applicants and set \(Y\) is a group of available jobs. Edges only exist between an applicant and a job they are qualified to do.
A complete bipartite graph, denoted by \(K_{r, s}\), occurs when every vertex in set \(X\) (where \(|X| = r\)) is connected to every vertex in set \(Y\) (where \(|Y| = s\)).
• Total number of vertices = \(r + s\)
• Total number of edges = \(r \cdot s\)
Matchings
A matching is a set of independent edges chosen such that no two edges share a common vertex.
A complete matching from set \(X\) to set \(Y\) (where \(|X| \le |Y|\)) is a matching in which every single vertex in set \(X\) is paired with a unique vertex in set \(Y\).
Hall's Marriage Theorem
How do we know if a complete matching is possible? Hall's Marriage Theorem gives the exact condition.
Let \(S\) be any subset of vertices in \(X\), and let \(N(S)\) be the neighbourhood of \(S\) (the set of all vertices in \(Y\) that are connected to at least one vertex in \(S\)).
Hall's Condition: A complete matching from \(X\) to \(Y\) exists if and only if for every subset \(S \subseteq X\):
\(|N(S)| \ge |S|\)
How to Show a Complete Matching Fails (Examiner Alert!):
If an exam question asks you to prove that a complete matching cannot be found, you must explicitly state a specific subset \(S \subseteq X\) and its corresponding neighbourhood \(N(S)\) such that:
\(|N(S)| < |S|\)
Example phrasing: "Consider the subset of applicants \(S = \{A_1, A_2, A_3\}\). Their combined qualified jobs are \(N(S) = \{J_1, J_2\}\). Since \(|S| = 3\) and \(|N(S)| = 2\), we have \(|N(S)| < |S|\). Therefore, by Hall's Marriage Theorem, no complete matching exists."
Key Takeaway: Bipartite graphs partition vertices into two sets with no internal edges. A complete matching pairs every member of set \(X\) uniquely. If any group of \(k\) vertices in \(X\) connects to fewer than \(k\) vertices in \(Y\), Hall's condition fails.
---3. Traversability: Eulerian and Hamiltonian Graphs
Students often mix up Eulerian trails and Hamiltonian cycles. Here is a simple distinction to keep them straight:
• Eulerian focuses on Edges (both start with the letter E).
• Hamiltonian focuses on Vertices / Houses (visiting every individual location).
Eulerian Graphs (Closed Eulerian Trail)
An Eulerian graph contains a closed trail that traverses every edge exactly once and returns to the starting vertex.
Condition: A connected graph is Eulerian if and only if every vertex has an even degree.
Semi-Eulerian Graphs (Open Eulerian Trail)
A semi-Eulerian graph contains an open trail that traverses every edge exactly once, but starts and finishes at different vertices.
Condition: A connected graph is semi-Eulerian if and only if it has exactly two vertices of odd degree.
• The trail must start at one odd vertex and finish at the other odd vertex.
Hamiltonian Graphs
A graph is Hamiltonian if it contains a Hamiltonian cycle: a closed loop that visits every vertex exactly once and returns to the start vertex.
Note: Unlike Eulerian graphs, there is no simple degree-parity rule to test if a graph is Hamiltonian just by looking at odd/even degrees. You must identify or construct the cycle explicitly.
Key Takeaway: All even degrees \(\implies\) Eulerian (all edges once, closed). Exactly two odd degrees \(\implies\) Semi-Eulerian (all edges once, open, start and end at odd vertices). Hamiltonian \(\implies\) visits every vertex once in a closed cycle.
---4. Graph Algorithms
In decision mathematics, algorithms provide systematic, step-by-step methods to solve network optimisation problems. You must follow the steps methodically and show all required working.
Minimum Spanning Trees (MST)
Given a connected, weighted graph with \(n\) vertices, a Minimum Spanning Tree connects all \(n\) vertices using exactly \(n - 1\) edges such that the total sum of edge weights is minimized.
Kruskal's Algorithm (Edge-by-Edge)
Kruskal's algorithm builds an MST by considering edges globally in order of weight:
Step 1: List all edges in non-decreasing order of weight (smallest to largest).
Step 2: Select the edge with the smallest weight.
Step 3: Add the next smallest edge on the list, provided it does not form a cycle with previously selected edges. If it creates a cycle, reject it.
Step 4: Repeat until you have added exactly \(n - 1\) edges.
Prim's Algorithm (Growing a Tree)
Prim's algorithm builds an MST by growing a single connected tree from a starting vertex:
Network Form:
Step 1: Choose an arbitrary starting vertex.
Step 2: Look at all edges connecting any vertex currently in the tree to any vertex not yet in the tree.
Step 3: Select the edge with the minimum weight and add this edge and new vertex to the tree.
Step 4: Repeat until all \(n\) vertices are included in the tree (total of \(n - 1\) edges).
Matrix Form:
Step 1: Choose a starting vertex. Cross out its row and put a number \(1\) above its column.
Step 2: Look at all un-crossed numbers in all numbered columns.
Step 3: Circle the smallest entry. The row of this entry gives the next vertex to add.
Step 4: Cross out that vertex's row and label its column with the next consecutive number (\(2, 3, \dots\)).
Step 5: Repeat until all rows are crossed out.
Examiner Tip: When asked to use Prim's algorithm, always state the order in which edges are selected to gain full method marks!
Dijkstra's Algorithm (Shortest Path)
Dijkstra's algorithm finds the shortest path from a given start vertex to all other vertices in a network with non-negative edge weights.
For each vertex, you must clearly show three elements:
1. Order of labelling: The sequence in which the vertex becomes permanent (\(1^{\text{st}}, 2^{\text{nd}}, 3^{\text{rd}}, \dots\)).
2. Permanent label: The final, confirmed shortest distance from the start vertex.
3. Working values (temporary labels): Intermediate calculated distances updated as the algorithm explores paths.
Step-by-Step Procedure:
Step 1: Assign the start vertex a permanent label of \(0\) and an order of labelling of \(1\).
Step 2: Calculate working values for all unlabelled vertices directly connected to the newly permanently labelled vertex.
\(\text{New working value} = \text{Permanent label of current vertex} + \text{Edge weight}\)
Note: If a vertex already has a working value, only replace it if the new value is smaller.
Step 3: Look at all unlabelled vertices across the entire graph. Select the one with the smallest working value.
Step 4: Make this value the vertex's permanent label and assign it the next order of labelling.
Step 5: Repeat Steps 2–4 until the destination vertex receives its permanent label.
Step 6 (Backtracking to reconstruct the path): To find the exact path, work backwards from the destination. A preceding vertex \(U\) is on the shortest path to \(V\) if:
\(\text{Permanent Label}(V) - \text{Weight of Edge}(U, V) = \text{Permanent Label}(U)\)
Common Dijkstra Mistakes to Avoid:
• Finding the path by eye/inspection without showing all intermediate working values.
• Forgetting to write down the order of labelling numbers.
• Failing to show the explicit backtracking step when stating the final path.
Key Takeaway: Kruskal sorts all edges globally and avoids cycles. Prim grows a single tree step-by-step from an initial node. Dijkstra systematically finds the shortest path by maintaining working values and assigning permanent labels in ascending order of distance.
---Summary Checklist for Revision
Before sitting your exam, make sure you can:
• State and apply the Handshaking Lemma (\(\sum d(v) = 2|E|\)) to verify degree sequences.
• Verify planar graphs using Euler's formula (\(V - E + F = 2\)) including the outer face.
• Check bipartite matchings using Hall's Condition (\(|N(S)| \ge |S|\)) and write clear failure statements.
• Distinguish between Eulerian (all even degrees), Semi-Eulerian (two odd degrees), and Hamiltonian graphs.
• Execute Kruskal's, Prim's (both network and matrix forms), and Dijkstra's algorithms with complete, step-by-step working.