Introduction to graph theory
(Redirected from School of Mathematics:Introduction to Graph Theory)
Introduction to Graph Theory
editAn introductory course from the School of Mathematics
This course aims to provide a thorough introduction to the subject of graph theory.
Course requirements
editThe 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
editThis 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
editAssignments
edit- Problems 1 (on Lectures 1-5)
- Problems 2 (on Lectures 6-10)