ASO: Graph Theory - Material for the year 2020-2021

We have updated our Undergraduate exams guidance in preparation for the Trinity Term examinations.

Please see our new webpages dedicated to TT exams.

Prof. Marc Lackenby
Course Term: 
Course Lecture Information: 

8 lectures

Course Overview: 

This course introduces some central topics in graph theory.

Learning Outcomes: 

By the end of the course, students should have an appreciation of the methods and results of graph theory. They should have a good understanding of the basic objects in graph theory, such as trees, Euler circuits and matchings, and they should be able to reason effectively about graphs.

Course Synopsis: 

Introduction. Paths, walks, cycles and trees. Euler circuits. Hamiltonian cycles. Hall's theorem. Application and analysis of algorithms for minimum cost spanning trees, shortest paths, bipartite matching and the Chinese Postman Problem.

Reading List: 

R. J. Wilson, Introduction to Graph Theory, 5th edition, Prentice Hall, 2010.

D.B. West, Introduction to Graph Theory, 2nd edition, Prentice Hall, 2001.