Course Materials
Main content blocks
- Lecturer: Profile: Oliver Riordan
Course information
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.
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.
Section outline
-
-
Self-study practice sheet, especially for those who did not do Part A Graph Theory (many of the questions are from the sheets for that course).
-
Some initial problems covering either revision of Part A graph theory or material in the course up to page 6 of the lecture notes. These questions will not be covered in the classes.
-
For the first class. Covers material from weeks 1 and 2. Section A is for self-study; solutions will be provided. The core material is Section B, to be handed in for the first class. Section C is optional, but compulsory for MFoCS students; solutions will be provided.