MATH4CO Graph Theory
Not offered in 2016
The graphs studied in this course are general incidence structures consisting of a set of vertices, a set of edges and an incidence relation between them. This general structure lends itself to modelling a multitude of different situations from distribution networks and data structures to timetabling and optimal assignments.
In this module we will concentrate on properties of graphs themselves and some techniques for working with them. The topics offered will vary from time to time, but will cover such areas as: Colouring problems (vertex and edge problems; the Four-Colour Theorem; snarks and where to find them); Matchings (covering a graph with independent edges; Hall's Marriage Theorem; Tutte's matching theorem); Connectivity (how well does a graph hold together?, how hard is it to break it apart?); Symmetry (vertices and edges of a graph fall into equivalence classes according to the automorphisms of the graph, studying these offers simplification of many proofs).
MATH 272 Discrete Mathematics
The module is internally assessed. There will be three written assignments and a small project (involving a report and presentation)