Mathematics
Te Tari Pāngarau me te Tatauranga
Department of Mathematics & Statistics

MATH4CO Graph Theory

First Semester
10 points
 

Description

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).

Prerequisites

MATH 272 Discrete Mathematics

Lecturer

Robert Aldred

Assessment

The module is internally assessed. There will be three written assignments and a small project (involving a report and presentation)

Final mark

While we strive to keep details as accurate and up-to-date as possible, information given here should be regarded as provisional. Individual lecturers will confirm teaching and assessment methods.