MATH3033 Graph Theory

15 creditsClass Size: 175

Module manager: Dr Nicola Gambino
Email: N.Gambino@leeds.ac.uk

Taught: Semester 1 (Sep to Jan) View Timetable

Year running 2020/21

Pre-requisite qualifications

(MATH2210 or MATH2230) or COMP2721 or COMP2941, or equivalent.

This module is mutually exclusive with

This module is not approved as a discovery module

Module summary

Graph theory is an important mathematical tool in many different areas, including linguistics, chemistry, operational research and computer science. The subject has a distinctive flavour in that many definitions are pictorially intuitive and can be stated easily. This allows us to state and tackle problems, including the famous puzzle of the bridges of Königsberg, quite rapidly. In the module, we will cover the basic ideas of graph theory, such as connectedness, trees, planar graphs, Eulerian and Hamiltonian graphs and the four colour problem. This will often involve translating intuitive ideas into mathematical proofs.

Objectives

To introduce students to some of the main concepts and modeling usefulness of graph theory, and to develop their ability to reason graph theoretically.

On completion of this module, students should be able to:
(a) identify basic examples of isomorphic and non-isomorphic pairs of graphs, and make simple deductions involving vertex degrees, connectedness and bipartite graphs;
(b) apply a selection of criteria related to Eulerian and Hamiltonian graphs;
(c) explain and apply the basic theorems for trees and planar graphs;
(d) understand and apply basic graph theoretic search algorithms, for example to find the block graph of a graph;
(e) show a knowledge of graph colourings of various types, and apply a range of techniques for identifying chromatic numbers for graphs.

Syllabus

A selection of topics from the following:

1. Basic definitions, vertex degrees, special kinds of graphs (e.g. complete, bipartite; regular).
2. Paths and cycles, connected graphs, trees.
3. Multiple connectivity, Menger’s Theorem, cut vertices and blocks, block graphs.
4. Eulerian graphs and applications, Hamiltonian graphs, including Dirac's theorem and techniques for identifying non-Hamiltonian graphs.
5. Combinatorial aspects, Cayley’s theorem, matchings, Hall’s theorem.
6. Planar graphs, Euler's theorem, Kuratowski's theorem (without proof).
7. Colourability, Graph colouring, the five-colour theorem for planar graphs, the four-colour theorem for planar graphs (without proof), Brook's theorem, edge colourings, Tait colourings, chromatic numbers of surfaces, applications of the Euler characteristic, Heawood's inequality and the map colour theorem.
8. Algebraic graph theory, adjacency matrices, strongly regular graphs, Friendship Theorem, matrix-tree theorem.
9. Digraphs, strong connectedness, Robbins’ Theorem, Eulerian digraphs, Hamiltonian and semi-Hamiltonian tournaments and Moon's Theorem.
10. Breadth-first-search and depth-first-search algorithms in graphs, finding cut-vertices and blocks.

Teaching methods

Due to COVID-19, teaching and assessment activities are being kept under review - see module enrolment pages for information

 Delivery type Number Length hours Student hours Lecture 17 1.00 17.00 Private study hours 133.00 Total Contact hours 17.00 Total hours (100hr per 10 credits) 150.00

Private study

There will be two weekly office hours for students to get additional help, depending on their needs.

Opportunities for Formative Feedback

Regular problem solving assignments

Methods of assessment

Due to COVID-19, teaching and assessment activities are being kept under review - see module enrolment pages for information

Exams
 Exam type Exam duration % of formal assessment Open Book exam 2 hr 30 mins 100.00 Total percentage (Assessment Exams) 100.00

Normally resits will be assessed by the same methodology as the first attempt, unless otherwise stated