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