AQA A-Level Further Mathematics Discrete mathematics: a complete overview of graphs, network algorithms, critical paths, linear programming and game theory

What Discrete mathematics actually demands

Discrete mathematics is one of the optional applied areas of AQA A-Level Further Mathematics. It is the modelling and optimisation strand, built on graphs, algorithms and decision-making. The examiners test methodical algorithm-following and clear presentation, because most marks come from showing each step rather than from a single final answer. This guide walks through all five topics, then sets out the exam patterns AQA repeats.

Graphs and networks

Graphs and networks establishes the vocabulary: vertices, edges, degree, paths and cycles, with the handshaking lemma that degrees sum to twice the number of edges. Special graphs include trees (connected, no cycles, $n - 1$ edges), complete graphs $K_n$ and bipartite graphs. The adjacency matrix records edges between vertices, and a graph is Eulerian exactly when it is connected with all even degrees, while a Hamiltonian graph has a cycle through every vertex.

Network algorithms

Network algorithms find optimal structures in weighted graphs. Kruskal's and Prim's algorithms build a minimum spanning tree; Dijkstra's algorithm finds the shortest path by assigning permanent labels in increasing order. The route inspection (Chinese postman) problem traverses every edge with least repetition by pairing odd-degree vertices, and the travelling salesperson problem is bounded above by nearest-neighbour and below by vertex deletion.

Critical path analysis

Critical path analysis schedules a project from a precedence table. A forward pass gives earliest event times (taking the maximum incoming time) and a backward pass gives latest times (taking the minimum outgoing time). The longest path is the critical path, whose length is the minimum completion time; critical activities have zero float. A Gantt chart then shows how to schedule activities within their float to manage the workforce.

Linear programming

Linear programming maximises or minimises a linear objective subject to linear constraints. Graphically, the constraints bound a feasible region and the optimum lies at a vertex, found by the vertex method or by sliding an objective line. For larger problems, slack variables turn inequalities into equations and the simplex algorithm pivots through the tableau until the objective row has no negative entries.

Game theory

Game theory analyses two-player zero-sum games from a pay-off matrix. Each player plays safe with the maximin (row player) or minimax (column player); if these coincide there is a saddle point and a stable solution. Dominance reduces a game by deleting weak strategies. With no saddle point, players use mixed strategies found by equating expected pay-offs, and larger games convert to a linear programming problem.

How Discrete mathematics is examined

A typical AQA profile for Discrete mathematics:

• Algorithm questions. Running Kruskal, Prim or Dijkstra and showing every step, or completing forward and backward passes.
• Optimisation. Formulating and solving a linear program graphically or by simplex, and interpreting the solution in context.
• Reasoning. Identifying Eulerian or Hamiltonian graphs, finding float and the critical path, and locating saddle points or mixed strategies.

Check your knowledge

A mix of recall and method questions across Discrete mathematics. Attempt them under timed conditions, then check against the solutions.

1. A graph has $8$ edges. Find the sum of the degrees of its vertices. (2 marks)
2. How many edges does the complete graph $K_4$ have? (2 marks)
3. How many edges are in a minimum spanning tree of a graph with $6$ vertices? (2 marks)
4. State the first step of Kruskal's algorithm. (2 marks)
5. Define the total float of an activity. (2 marks)
6. Where does the optimum of a linear program occur? (1 mark)
7. Introduce a slack variable to turn $x + 4y \leq 20$ into an equation. (2 marks)
8. A game has maximin $5$ and minimax $5$. State the value of the game. (1 mark)