Module manager: TBC
Email: TBC
Taught: Semester 2 (Jan to Jun) View Timetable
Year running 2026/27
None
| MATH2130 | Further Linear Algebra and Discrete Mathematics |
MATH3033 Graph Theory MATH3143 Combinatorics
This module is not approved as a discovery module
Given a collection of things (in mathematical language, a set) a fundamental question in mathematics is: ‘How many things are in the collection?’. Combinatorics is the study of methods for counting the elements of finite sets. A graph, or network, is a set together with a collection of pairs of elements, expressing a connectedness between those elements. Clearly there is more to a graph than just the number of elements or the number of pairs. So Graph Theory is the study of graphs, or networks, and their structure. Graphs can be drawn as points and edges, and hence studied geometrically, answering questions such as whether it is possible to implement a given electronic circuit design in the plane. They can be studied combinatorially, answering questions such as how many graphs there are with certain properties, and how many paths with good properties there are in a given graph. Both topics have strong real-world applications, playing roles, for example, in evolutionary biology (e.g. phylogenetic trees and genetics), statistical physics (e.g. counting states of an object to determine its properties); computer science (e.g. in the study of algorithms and data structures) and transport system design (e.g. transport networks). This module will develop the theory of combinatorics and graph theory , ready for application. It also has the purer aim of drawing out the strong parallels and interactions between them.
The objectives of the module are to provide a strong foundation in the theories and general application of graph theory and combinatorics, drawing out common themes between the two subjects. The module will equip students with techniques for counting sets of objects. The main themes here considered will include fundamental counting principles, configurations of mathematical objects under constraints, the partition of sets of objects into subsets in a structured way, sequences of sets indexed by the natural numbers and the enumeration of graph-theoretic objects. The module will also equip students with an understanding of graphs and their properties. The main objectives are to make students familiar with fundamental properties of graphs, special families of graphs, the structure of graphs, geometric properties of graphs, subgraphs with various properties and algebraic techniques for studying graphs. Graph theory and combinatorics can give rise to powerful tools, so we will also consider ethical aspects of these topics.
On successful completion of the module students will be able to: 1. Use the methods from the course to determine the number of elements in a set and to determine fundamental properties of a graph, and similar problems. 2. Find examples of mathematical objects or graphs with given combinatorial or graph-theoretic properties. 3. Recall and apply appropriate methods and results of the course to combinatorial or graph-theoretic problems. 4. Give proofs of basic statements relating to combinatorial and graph-theoretic situations. 5. Describe connections between fundamental topics in combinatorics and graph theory.
Fundamental counting principles; Configurations and partition of mathematical objects under constraints; Sequences of sets indexed by the natural numbers, all defined in a common way; Fundamental notions and structure of graphs; Special kinds of graphs; Geometric properties of graphs; Subgraphs with various properties, including forbidden subgraphs; Enumeration of graph-theoretic objects; Additional topics that build on these may be covered as time allows. Such topics may be drawn from the following, or similar: Algebraic techniques for studying graphs; Counting colourings of graphs; Using inclusion-exclusion techniques to count subgraphs with certain properties, such as subgraphs without edges and complete subgraphs; Possibilities for complete subgraphs of a coloured graph whose edges all have the same colour (Ramsey theory)
| Delivery type | Number | Length hours | Student hours |
|---|---|---|---|
| Lecture | 44 | 1 | 44 |
| Private study hours | 156 | ||
| Total Contact hours | 44 | ||
| Total hours (100hr per 10 credits) | 200 | ||
Regular written formative coursework with feedback to students.
Check the module area in Minerva for your reading list
Last updated: 30/04/2026
Errors, omissions, failed links etc should be notified to the Catalogue Team