Introduction to graph theory

Introduction to Graph Theory edit

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

The following knowledge is required or desirable on commencement of study of this course:

Course outline edit

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

List of Definitions

Assignments edit