# Module Details

## MA314-7-SP-CO: Graph Theory

Year: 2017/18
Department: Mathematical Sciences
Essex credit: 15
ECTS credit: 7.5
Available to Study Abroad / Exchange Students: No
Full Year Module Available to Study Abroad / Exchange Students for a Single Term: No
Outside Option: No

Staff
Supervisor: Dr Gerald Williams
Teaching Staff: Dr Gerald Williams, email gwill@essex.ac.uk
Contact details: Miss Shauna McNally - Graduate Administrator. email: smcnally (Non essex users should add @essex.ac.uk to create the full email address), Tel 01206 872704

 Module is taught during the following terms Autumn Spring Summer

### Module Description

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

On completion of the module, students should be able to:
- Give basic graph theoretic definitions
- Prove basic results in the theory of graphs
- Deal with basic theory about: matchings (Hall's theorem, etc.) and similar topics, e.g. max-flow min cut, Dilworth
- Know some basic results about Hamilton cycles
- Have some experience of problems connected with chromatic number, and know basic theory
- Know rudiments of extremal graph theory, Ramsey theory and the theory of random graphs
- Be acquainted with use of MAPLE to investigate graph-theoretic problems.

Syllabus

Basics
Basic definitions: degrees, walks, trails, trees: minimum spanning tree. Bipartite graphs. Cycles, Hamiltonian cycles, connectedness, connectivity. Planar graphs (not too much topological detail).

Matchings
Definition. Hall's theorem on matching in bipartite graphs: results equivalent to Hall's theorem. Some discussion of Tutte's theorem and algorithmic aspects.

Connectivity
Menger's theorem, related results. Inequalities between
measures of connectivity.

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

Colouring Chromatic number. Greedy colouring algorithm, its use to prove Brooks' theorem. Edge chromatic number: Vizing's theorem. Choosability: Galvin and Thomassen's results. Brief informal discussion of the four-colour problem.

Extremal Graph Theory
Turan's theorem (with proof). Erdos-Stone theorem (without proof). Examples.

Ramsey theory

Basic definitions. Erdos-Szekeres upper bound. Probabilistic lower bound on diagonal Ramsey numbers.

Linear Algebra Methods
Adajacency matrix and spectrum. Laplacian. Some links with graph structure. Fisher's inequality for designs.

Random Graphs
G(n,p). Thresholds. First and second moment methods. Simple examples. Brief informal overview of the evolution of random graphs.

### Learning and Teaching Methods

There are 5 lectures and 2 classes in every fortnight. There will be different coursework at postgraduate level, and separate classes for postgraduates. In the Summer Term 3 revision lectures are given.

### Assessment

20 per cent Coursework Mark, 80 per cent Exam Mark

### Coursework

The coursework comprises a test worth 12.5%, a project worth 7.5% and 5 formative homeworks

### Other details

Information about coursework deadlines can be found in the "Coursework Information" section of the Current Students, Useful Information Maths web pages: Coursework and Test Information

### Exam Duration and Period

2:00 during Summer Examination period.

### Other information

Available to Socrates/IP students spending all relevant terms at Essex.