Aims: To introduce graph theory and some key definitions, and some proof techniques associated with graph theory.

On completion of the module, students should be able to:

- give basic graph theoretic definitions;

- apply basic results in the theory of graphs;

- deal with basic theory about matchings (Hall's theorem) and similar topics, e.g. max-flow min cut, Dilworth's theorem;

- apply basic results about Hamilton cycles;

- solve problems connected with chromatic number, and know basic theory;

- apply results concerning strongly regular graphs;

- know rudiments of extremal graph theory, Ramsey theory and the theory of random graphs.

** Syllabus **

** Basics ** Basic definitions: degrees, walks, trails, trees: minimum spanning tree. Bipartite graphs. Cycles, Hamiltonian cycles, connectedness, connectivity, planar graphs.

** Matchings **

Definition. Hall's theorem on matching in bipartite graphs.

** Connectivity **

Inequalities between various measures of connectivity.

** Hamilton cycles **

Dirac's theorem and its variants. Chvatal-Erdos theorem.

** Colouring **

Chromatic number, Brooks' theorem, edge chromatic number, Vizing's theorem, choosability. Brief discussion of the four-colour problem.

** Extremal Graph Theory **

Turan's theorem, Erdos-Stone theorem. Examples.

** Ramsey theory **

Basic definitions, Erdos-Szekeres upper bound.

** Linear Algebra Methods **

Adjacency matrix and spectrum. Some links with graph structure.

** Random graphs **

G(n,p). Thresholds. First moment method.

- Module Supervisor: David Penman