Module and Programme Catalogue

Search site

Find information on

2019/20 Undergraduate Module Catalogue

MATH3033 Graph Theory

15 creditsClass Size: 110

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

Taught: Semester 1 (Sep to Jan) View Timetable

Year running 2019/20

Pre-requisite qualifications

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

This module is mutually exclusive with

MATH5033MAdvanced Graph Theory

This module is not approved as a discovery module

Module summary

This module provides an introduction to the basic ideas such as connectedness, trees, planar graphs, Eulerian and Hamiltoniangraphs, directed graphs and the connection between graph theory and the four colour problem.Graph theory is an important mathematical tool in such different areas as linguistics, chemistry and, especially, operational research. This module will include some abstract 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, planar graphs and directed 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 and surfaces.

Syllabus

Topics chosen from:
1. Basic definitions. Connected graphs, vertex degrees, bipartite graphs.
2. Adjacency matrices, strongly regular graphs, Friendship Theorem.
3. Eulerian graphs and applications.
4. Hamiltonian graphs, including Dirac's theorem and techniques for identifying non-Hamiltonian graphs.
5. Trees (Cayley's Theorem), line graphs. Multiple connectivity and block graphs.
6. Planar graphs. Euler's theorem, Kuratowski's theorem (without proof).
7. Digraphs, strong connectedness. Robbins' Theorem. Eulerian digraphs. Hamiltonian and semi-Hamiltonian tournaments and Moon's Theorem.
8. Breadth-first-search and depth-first-search algorithms in graphs; finding cut-vertices and blocks.
9. Graph colourings. The five-colour theorem for planar graphs, the four-colour theorem for planar graphs (without proof). Brook's Theorem. Edge colourings, Tait colourings.
10. Chromatic numbers of surfaces, applications of the Euler characteristic, Heawood's inequality and the Map Colour Theorem.

Teaching methods

Delivery typeNumberLength hoursStudent hours
Lecture331.0033.00
Private study hours117.00
Total Contact hours33.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


Exams
Exam typeExam duration% of formal assessment
Standard exam (closed essays, MCQs etc)2 hr 30 mins100.00
Total percentage (Assessment Exams)100.00

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

Reading list

The reading list is available from the Library website

Last updated: 20/05/2019

Disclaimer

Browse Other Catalogues

Errors, omissions, failed links etc should be notified to the Catalogue Team.PROD

© Copyright Leeds 2019