Introduction to graph theory

Introduction to Graph Theory

An introductory course from the School of Mathematics

This course aims to provide a thorough introduction to the subject of graph theory.

Course requirements

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

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

• 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

List of Definitions

Assignments

• Problems 1 (on Lectures 1-5)
• Problems 2 (on Lectures 6-10)