- Lecturer: Paul Balister
General Prerequisites:
Part A Graph Theory is recommended.
Course Term: Michaelmas
Course Lecture Information: 16 lectures
Course Weight: 1
Course Level: H
Assessment Type: Written Examination
Course Overview:
Graphs (abstract networks) are among the simplest mathematical structures, but nevertheless have a very rich and well-developed structural theory. Since graphs arise naturally in many contexts within and outside mathematics, Graph Theory is an important area of mathematics, and also has many applications in other fields such as computer science.
The main aim of the course is to introduce the fundamental ideas of Graph Theory, and some of the basic techniques of combinatorics.
The main aim of the course is to introduce the fundamental ideas of Graph Theory, and some of the basic techniques of combinatorics.
Learning Outcomes:
The student will have developed a basic understanding of the properties of graphs, and an appreciation of the combinatorial methods used to analyze discrete structures.
Course Synopsis:
Introduction: basic definitions and examples. Trees and their characterization. Euler circuits; long paths and cycles. Vertex colourings: Brooks' theorem, chromatic polynomial. Edge colourings: Vizing's theorem. Planar graphs, including Euler's formula, dual graphs. Maximum flow - minimum cut theorem: applications including Menger's theorem and Hall's theorem. Tutte's theorem on matchings. Extremal Problems: Turan's theorem, Zarankiewicz problem, Erdős-Stone theorem.