Module overview
Aims and Objectives
Learning Outcomes
Learning Outcomes
Having successfully completed this module you will be able to:
- Be able to state and apply the definitions of and the fundamental results describing the behaviour of graph properties as described in the syllabus; and determine whether these properties hold for specific examples and classes of graphs, as well as for graph constructions
- Be able to state the definitions of numerical invariants associated to graphs as described in the syllabus; to use these definitions in proofs; and to calculate these invariants for specific examples and classes of graphs, as well as for graph constructions
Syllabus
• Definitions of basic numerical quantities of graphs, including diameter and radius, minimum and maximum degree, girth and circumference, chromatic number and chromatic index, clique number and independence number; other invariants may be included beyond these;
• Eulerian graphs, and necessary and sufficient conditions for a graph to be Eulerian;
• Hamiltonian graphs, and sufficient conditions for a graph to be Hamiltonian, including Ore’s Theorem;
• Trees, including Prufer sequences and Cayley’s theorem for the number of spanning trees of a complete graph;
• Planar graphs, including the statement, proof and applications of Euler’s formula; the statement (but not the proof) of Kuratowski’s theorem.
• Vertex colourings of graphs, including the greedy algorithm for producing a vertex colouring and the statement of Brooks’ theorem;
• Vertex colourings of planar graphs, including the statement and proof of the five colour theorem, and the statement of the four colour theorem;
• Edge colourings of graphs, including edge colourings of bipartite graphs, and the statements of Vizing’s theorem and Koenig’s theorem.
• Basic definitions and properties of random graphs; Erdos’s theorem on the existence of graphs with large girth and large chromatic number.
Learning and Teaching
Teaching and learning methods
Lectures, weekly tutorials, regular exercises, private study
| Type | Hours |
|---|---|
| Teaching | 48 |
| Independent Study | 102 |
| Total study time | 150 |
Assessment
Summative
This is how we’ll formally assess what you have learned in this module.
| Method | Percentage contribution |
|---|---|
| Coursework | 100% |
Referral
This is how we’ll assess you if you don’t meet the criteria to pass this module.
| Method | Percentage contribution |
|---|---|
| Coursework | 100% |
Repeat
An internal repeat is where you take all of your modules again, including any you passed. An external repeat is where you only re-take the modules you failed.
| Method | Percentage contribution |
|---|---|
| Coursework | 100% |