Module Title  Graph Theory 
School  Mathematics 
Department  Mathematics 
Module Code  06 19605 
Module Lead  Deryk Osthur & Allan Lo 
Level  Masters Level 
Credits  20 
Semester  Semester 1 
Prerequisites 
LC Algebra & Combinatorics 1  (06 25659)

Corequisites 

Restrictions  Optional for all MSci programmes in Mathematics and all MSci JH programmes including Mathematics 
Contact Hours 
Lecture46 hours
Tutorial10 hours
Total: 56 hours

Exclusions  
Description  The module will give an introduction to fundamental results and concepts in graph theory. Topics are likely to include Hamilton cycles, graph matchings, connectivity, graph colourings, planar graphs and extremal graph problems. For example a fundamental result in Graph Theory is Dirac's theorem. It gives a condition which ensures that a graph has a Hamilton cycle (ie a cycle which contains all vertices of the graph). Another example is the four colour theorem. It states that every planar map can be coloured with at most four colours such that adjacent regions have different colours (this can be translated into a graph colouring problem). Some of the ideas will also be applied to algorithmic problems for graphs. 
Learning Outcomes  By the end of the module the student should be able to: Be familiar with basic graph parameters and their relationships
 Understand and be able to apply fundamental results on graphs
 Understand how some problems can be modelled as algorithmic graph problems and should know approaches to solve them
 Apply the basic techniques introduced in the lectures
 Explore these topics beyond the taught syllabus

Assessment 
1960507 : Raw Module Mark : Coursework (100%)

Assessment Methods & Exceptions  2 hour Written Unseen January Examination (80%); Incourse Assessment (20%). 
Other  
Reading List 
West, D. 2001. Introduction to Graph Theory. Prentice Hall.
Diestel, R. 2000. Graph Theory. 2nd ed. Springer Verlag.
Electronic Version: http://www.ecp6.jussieu.fr/pageperso/bondy/books/gtwa/gtwa.html
Bondy, J A & Murty, U S R. 1976. Graph Theory with Applications. NorthHolland.
