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

## Primary tabs

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

**Please see our new webpages dedicated to TT exams.**

8 lectures

This course introduces some central topics in graph theory.

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.

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.

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

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