What is the difference between an Eulerian circuit and a Hamiltonian cycle?

An Eulerian circuit is a closed trail that uses every edge of a graph exactly once, while a Hamiltonian cycle is a closed trail that visits every vertex exactly once. Eulerian circuits focus on edges, Hamiltonian cycles on vertices. A graph can have one without the other.

How do I know when to use permutations vs combinations?

Use permutations when the order of selection matters (e.g., arranging books on a shelf). Use combinations when order does not matter (e.g., choosing a committee). The key question: does swapping two items produce a different outcome? If yes, use permutations.

What is the pigeonhole principle and how is it used in exams?

The pigeonhole principle states that if n items are placed into m containers and n > m, then at least one container contains more than one item. In exams, it is used to prove existence results, such as showing that in any group of 13 people, at least two share a birth month.

Can Dijkstra's algorithm handle negative weights?

No, Dijkstra's algorithm assumes all edge weights are non-negative. If negative weights are present, the algorithm may produce incorrect results. Use the Bellman-Ford algorithm instead, which can handle negative weights but is slower.

What is a recurrence relation and how do I solve one?

A recurrence relation defines each term of a sequence as a function of previous terms. For linear homogeneous recurrences with constant coefficients, solve by finding the characteristic equation, finding its roots, and writing the general solution as a linear combination of exponentials. For example, for a_n = 5a_{n-1} - 6a_{n-2}, the characteristic equation is r^2 - 5r + 6 = 0, giving r=2,3, so a_n = A*2^n + B*3^n.

How do I find a minimum spanning tree using Prim's algorithm?

Start from any vertex. Repeatedly add the cheapest edge that connects a vertex already in the tree to a vertex not yet in the tree, without forming cycles. Continue until all vertices are included. Prim's algorithm is greedy and works well for dense graphs.

Discrete Mathematics

OCR

A-Level

This subtopic introduces the fundamental categorisation of discrete problems into existence, construction, enumeration, and optimisation. It also covers essential counting techniques, including set notation, partitions, the pigeonhole principle, and the multiplicative principle, which serve as a foundation for further study in Discrete Mathematics.

Objectives

Exam Tips

Pitfalls

Key Terms

Mark Points

Subtopics in this area

Mathematical Preliminaries

Graphs and Networks

Algorithms

Network Algorithms

Decision Making in Project Management

Graphical Linear Programming

The Simplex Algorithm

Game Theory

Topic Overview

Discrete Mathematics is a branch of mathematics dealing with objects that can assume only distinct, separated values. In the OCR A-Level Further Mathematics specification, it encompasses topics such as graph theory, combinatorics, and algorithms. This area is fundamental to computer science, operations research, and network analysis, providing tools for solving problems involving finite sets, counting, and optimisation. Understanding discrete mathematics enables you to model real-world situations like scheduling, route planning, and resource allocation.

The course covers key areas including graph theory (e.g., Eulerian and Hamiltonian graphs, planar graphs), network algorithms (e.g., Dijkstra's algorithm, minimum spanning trees), and combinatorial methods (e.g., permutations, combinations, the pigeonhole principle). You will also study recurrence relations, generating functions, and finite state machines. These topics build logical reasoning and algorithmic thinking, which are essential for further study in mathematics, computer science, and engineering.

Mastering discrete mathematics is crucial for success in the OCR A-Level Further Mathematics exams, as it appears in both pure and applied papers. It also provides a foundation for university-level courses in computer science, cryptography, and discrete mathematics. By learning to think in terms of discrete structures and algorithms, you develop problem-solving skills that are highly valued in STEM careers.

Key Concepts

Core ideas you must understand for this topic

→Graph Theory: Understand definitions of graphs, vertices, edges, degrees, paths, cycles, and connectivity. Know Eulerian and Hamiltonian graphs, including necessary and sufficient conditions.
→Algorithms: Be able to apply Dijkstra's algorithm for shortest paths, Kruskal's and Prim's algorithms for minimum spanning trees, and understand the concept of complexity (big O notation).
→Combinatorics: Master counting principles including the addition and multiplication rules, permutations, combinations, and the binomial theorem. Apply the pigeonhole principle to solve problems.
→Recurrence Relations: Solve linear homogeneous recurrence relations with constant coefficients, and use generating functions to find closed forms.
→Finite State Machines: Understand deterministic finite automata (DFA), state transition diagrams, and the concept of acceptance of strings.

What You Need to Demonstrate

Key skills and knowledge for this topic

Correct classification of problems into existence, construction, enumeration, or optimisation categories.
Accurate use of set notation and terminology, including partitions.
Correct application of the pigeonhole principle to solve counting problems.
Accurate use of the multiplicative principle for counting arrangements.
Correct calculation of permutations (nPr) and combinations (nCr).
Correct enumeration of arrangements with constraints (repetition and restriction).
Correct application of the inclusion-exclusion principle for two sets.
Correct use of terminology: vertex (node), arc (edge), degree, adjacent, walk, trail, path, cycle, route.

Marking Points

Key points examiners look for in your answers

Correct classification of problems into existence, construction, enumeration, or optimisation categories.
Accurate use of set notation and terminology, including partitions.
Correct application of the pigeonhole principle to solve counting problems.
Accurate use of the multiplicative principle for counting arrangements.
Correct calculation of permutations (nPr) and combinations (nCr).
Correct enumeration of arrangements with constraints (repetition and restriction).
Correct application of the inclusion-exclusion principle for two sets.
Correct use of terminology: vertex (node), arc (edge), degree, adjacent, walk, trail, path, cycle, route.
Identification of graph types: tree, simple, connected, simply connected, complete (Kn), bipartite (Km,n).
Application of degree sequence and colouring arguments for isomorphism and bipartiteness.
Correct application of Eulerian and Hamiltonian graph definitions and theorems (e.g., Ore's theorem).
Use of Euler's formula (V + R = E + 2) for planar graphs.
Application of Kuratowski's theorem regarding planarity.
Correct use of adjacency matrices and weighted matrix representations.
Correct tracing of algorithms presented as flow diagrams, pseudo-code, or word descriptions.
Correct identification of the order of an algorithm (e.g., O(n^k)) and calculation of approximate run-time by scaling.
Correct application of sorting algorithms: bubble sort, shuttle sort, and quick sort.
Correct application of packing algorithms: next-fit, first-fit, first-fit decreasing, and full bin methods.
Correct use of INT(x) and ABS(x) functions within algorithmic steps.
Understanding of the hierarchy of orders (e.g., O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(n^3) < O(a^n) < O(n!)).
Correct application of Dijkstra’s algorithm to find the shortest path.
Correct application of Prim’s or Kruskal’s algorithm to find a minimum spanning tree.
Correct use of the nearest neighbour method to find an upper bound for the Travelling Salesperson problem.
Correct use of a minimum spanning tree on a reduced network to find a lower bound for the Travelling Salesperson problem.
Correct solution of the route inspection problem by considering all possible pairings of odd nodes.
Clear demonstration of the algorithm process rather than just the final answer.
Correct interpretation of network problems in context.
Construction and interpretation of activity networks using activity on arc.
Execution of forward pass to determine earliest start times and minimum project completion time.
Execution of backward pass to determine latest finish times and identify critical activities.
Calculation and interpretation of total float, independent float, and interfering float.
Construction of cascade charts to determine the effect of delays or scheduling restrictions on project completion.
Construction of schedules for a given number of workers subject to constraints.
Correct formulation of the objective function and constraints
Accurate plotting of constraint lines on a graph
Correct identification of the feasible region
Correct identification of the optimal point (vertex) within the feasible region
Correct handling of integer constraints where applicable
Setting up the initial simplex tableau in standard format
Correct identification of the pivot column (most negative value in the objective row)
Correct identification of the pivot row (minimum non-negative ratio of RHS to pivot column)
Performing correct row operations to update the tableau
Correct interpretation of the final tableau to identify the optimal solution
Correct identification of basic and non-basic variables at each stage
Correct identification of zero-sum games and construction of pay-off matrices.
Application of dominance arguments to reduce the size of pay-off matrices.
Identification of play-safe strategies and stable solutions (saddle points).
Identification of Nash Equilibrium solutions.
Calculation of optimal mixed strategies using simultaneous equations or graphical methods.
Reformulation of games without stable solutions as linear programming problems for solution via the simplex algorithm.

Examiner Tips

Expert advice for maximising your marks

💡Always check if the order of items matters before deciding between permutations and combinations.
💡For arrangement problems with restrictions, try listing small cases or using a diagram to visualise the constraints.
💡When using the inclusion-exclusion principle, clearly define the sets involved to avoid double-counting.
💡Show clear working for counting problems; marks are often awarded for the method even if the final arithmetic is incorrect.
💡Use the notation nPr and nCr correctly as specified in the formulae booklet.
💡When asked to show two graphs are isomorphic, provide a clear mapping of vertices or a reasoned argument based on invariant properties.
💡Always check if a graph is simple before applying theorems like Ore's.
💡Use clear, labelled diagrams when constructing planar representations.
💡Remember that Ore's theorem provides a sufficient, but not necessary, condition for a graph to be Hamiltonian.
💡When using adjacency matrices, ensure the matrix is correctly constructed for the given graph type (directed vs undirected).
💡Use the Formulae Booklet for the hierarchy of orders; do not rely on memory for complex order relationships.
💡When tracing an algorithm, keep a clear table of variable values at each step to avoid errors.
💡If a question asks for a specific algorithm (e.g., Dijkstra's or a sorting algorithm), you must use that method; do not use inspection.
💡Remember that heuristic algorithms (like packing methods) do not guarantee an optimal solution.
💡Show all working for algorithm traces, as marks are awarded for the process, not just the final output.
💡Only use specific algorithms if instructed to do so in the question.
💡Use the Formulae Booklet for sketches of algorithms; focus on understanding the process.
💡Show detailed reasoning for algorithm steps; do not just write down the final result.
💡Be prepared to adapt an algorithm or solution to deal with practical issues.
💡Use technology in the classroom to demonstrate large-scale problems, but expect small-scale problems in the assessment.
💡Use the provided Formulae Booklet for algorithm sketches, but focus on understanding the underlying theory rather than rote memorization.
💡Demonstrate understanding of the application of algorithms to small-scale problems as required in the assessment.
💡Ensure clear communication of the critical path and float calculations in the context of the project.
💡Practice constructing cascade charts to visualize scheduling constraints effectively.
💡Use a sharp pencil and ruler for accurate graph plotting
💡Clearly label all constraint lines and the feasible region
💡Check the objective function value at all vertices of the feasible region to ensure the true optimum is found
💡Use graphing software during practice to investigate the effects of changing coefficients
💡Ensure the objective row is correctly formatted before starting iterations
💡Always show clear working for row operations to allow for method marks
💡Check for negative values in the objective row to determine if further iterations are required
💡Use the provided Formulae Booklet for standard algorithm steps if necessary
💡Be prepared to explain the algebraic calculations used in the algorithm
💡Always check for a stable solution (saddle point) first before attempting more complex methods.
💡Use dominance arguments to simplify the pay-off matrix as much as possible before starting calculations.
💡Ensure you can clearly distinguish between the perspectives of the two players in a zero-sum game.
💡Be prepared to use the simplex algorithm as a tool for solving mixed strategy games when graphical methods are not applicable.
💡When solving graph theory problems, always draw a clear diagram and label vertices and edges. This helps avoid mistakes and shows the examiner your reasoning.
💡For algorithm questions, show each step of the algorithm (e.g., Dijkstra's table) even if you can do it mentally. Partial marks are awarded for correct intermediate steps.
💡In combinatorics, clearly state whether order matters (permutations) or not (combinations) and use the correct formula. Check if repetition is allowed.

Common Mistakes

Pitfalls to avoid in your exam answers

Confusing permutations (where order matters) with combinations (where order does not matter).
Failing to account for constraints (e.g., items not being next to each other) when calculating arrangements.
Misapplying the inclusion-exclusion principle by failing to subtract the intersection correctly.
Incorrectly identifying the number of objects or the nature of the restriction in arrangement problems.
Misinterpreting the pigeonhole principle in non-obvious scenarios.
Confusing the definitions of walk, trail, path, and cycle.
Assuming that having the same degree sequence is sufficient to prove isomorphism.
Misapplying Ore's theorem by failing to check if the graph is simple or if the condition holds for all non-adjacent pairs.
Incorrectly identifying a graph as bipartite without a valid colouring argument.
Failing to correctly identify odd-degree vertices when determining if a graph is Eulerian or semi-Eulerian.
Confusing the order of an algorithm with its actual run-time for a specific small input.
Incorrectly applying sorting algorithms (e.g., starting bubble sort from the wrong end or choosing the wrong pivot for quick sort when specified).
Failing to correctly identify the 'worst case' scenario when calculating time complexity.
Misinterpreting the hierarchy of orders, particularly for exponential or factorial complexities.
Applying heuristic packing algorithms without following the specific rules for that algorithm.
Confusing the requirements of different network algorithms (e.g., Prim's vs Kruskal's).
Failing to consider all possible pairings of odd nodes in the route inspection problem.
Incorrectly identifying the number of odd nodes in a network.
Misinterpreting the conditions for a lower bound in the Travelling Salesperson problem when the graph is not complete.
Rote application of algorithms without understanding the underlying theory.
Failure to show sufficient working for the algorithm steps.
Confusing total float with independent or interfering float.
Errors in the forward or backward pass calculations leading to incorrect critical path identification.
Misinterpreting the 'activity on arc' notation.
Failing to correctly identify all critical activities in complex networks.
Incorrectly shading the feasible region
Failing to include non-negativity constraints
Misinterpreting the objective function when finding the optimal point
Assuming the optimal solution must be an integer when the problem does not specify integer programming
Incorrect choice of pivot column or pivot row
Errors in arithmetic during row operations
Failing to correctly identify when the optimum has been achieved
Misinterpreting the values of slack variables in the final tableau
Incorrectly setting up the initial tableau from the problem constraints
Failing to correctly identify or reduce a game using dominance arguments before attempting further calculations.
Confusing pure strategies with mixed strategies when solving for optimal outcomes.
Incorrectly setting up the linear programming formulation for mixed strategies.
Misinterpreting the meaning of a Nash Equilibrium in the context of the game.
Misconception: Eulerian circuits require all vertices to have even degree. Correction: For an Eulerian circuit, every vertex must have even degree, but for an Eulerian trail, exactly two vertices have odd degree.
Misconception: Dijkstra's algorithm works with negative edge weights. Correction: Dijkstra's algorithm fails with negative weights; use Bellman-Ford instead.
Misconception: The pigeonhole principle only applies to pigeons and holes. Correction: It is a general counting principle: if n items are placed into m boxes and n > m, then at least one box contains more than one item.

Frequently Asked Questions

Common questions students ask about this topic

Before You Start

Prior knowledge that will help with this topic

•A-Level Mathematics: Basic algebra, functions, and probability are essential.
•GCSE Mathematics: Familiarity with sets, Venn diagrams, and basic counting.
•Logical reasoning: Ability to follow and construct simple proofs.

Likely Command Words

How questions on this topic are typically asked

Find

Calculate

Show

Explain

Determine

Understand

Use

Construct

Identify

Apply

Model

Trace

Sort

Compare

Solve

Demonstrate

Interpret

Formulate

Discuss

Set up

Perform

Reduce

Ready to test yourself?

Practice questions tailored to this topic

Discrete Mathematics

Subtopics in this area

Topic Overview

Key Concepts

What You Need to Demonstrate

Marking Points

Examiner Tips

Common Mistakes

Frequently Asked Questions

Before You Start

Likely Command Words

Ready to test yourself?

Related Topics in OCR A-Level Further Mathematics

Mechanics

Statistics

Pure Core

Statistics

How to Revise Discrete Mathematics — OCR A-Level Further Mathematics

Examiner Tips for Discrete Mathematics

Common Mistakes in Discrete Mathematics

Key Marking Points

Discrete Mathematics

Subtopics in this area

Topic Overview

Key Concepts

What You Need to Demonstrate

Marking Points

Examiner Tips

Common Mistakes

Frequently Asked Questions

What is the difference between an Eulerian circuit and a Hamiltonian cycle?

How do I know when to use permutations vs combinations?

What is the pigeonhole principle and how is it used in exams?

Can Dijkstra's algorithm handle negative weights?

What is a recurrence relation and how do I solve one?

How do I find a minimum spanning tree using Prim's algorithm?

Before You Start

Likely Command Words

Ready to test yourself?

Related Topics in OCR A-Level Further Mathematics

Mechanics

Statistics

Pure Core

Statistics