# 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

edit## Assignments

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