Introduction to graph theory
Introduction to Graph Theory
[edit | edit source]An introductory course from the School of Mathematics
This course aims to provide a thorough introduction to the subject of graph theory.
Course requirements
[edit | edit source]The following knowledge is required or desirable on commencement of study of this course:
- knowledge of basic methods of proof
- knowledge of basic probability
Course outline
[edit | edit source]This is an approximate depiction of the course:
- Definitions
- Bipartite Graphs
- Hamilton Cycles and Eulerian Circuits
- Planar Graphs
- Statement of Kuratowski's Theorem
- Matchings in Bipartite Graphs
- Hall's Theorem
- Connectivity
- Menger's Theorem
- Extremal Graph Theory
- Hamilton and other cycles
- Turan's Theorem
- Ramsey's Theorem
- Graph Colourings
- Chromatic Polynomial
- Vizing's Theorem
- Four-Colour and Five-Colour Theorems
- Extensions to other surfaces
- Eigenvalues
- Applications to Strongly Regular Graphs
- The Probabilistic Method
- Lower bounds for Ramsey numbers
- Graphs with large girth and chromatic number
Lecture series
[edit | edit source]- Lecture 1 Introduction and Definitions
- Lecture 2 Bipartite Graphs and Trees
- Lecture 3 Hamilton Cycles and Eulerian Circuits
- Lecture 4 Graph Traversal
- Lecture 5 Flows and Cuts
- Lecture 6 Planar Graphs
Assignments
[edit | edit source]- Problems 1 (on Lectures 1-5)
- Problems 2 (on Lectures 6-10)