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.
Basics Basic definitions: degrees, walks, trails, trees: minimum spanning tree. Bipartite graphs. Cycles, Hamiltonian cycles, connectedness, connectivity, planar graphs.
Definition. Hall's theorem on matching in bipartite graphs.
Inequalities between various measures of connectivity.
Dirac's theorem and its variants. Chvatal-Erdos theorem.
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.
Basic definitions, Erdos-Szekeres upper bound.
Linear Algebra Methods
Adjacency matrix and spectrum. Some links with graph structure.
G(n,p). Thresholds. First moment method.
- Module Supervisor: David Penman