School of Computing and Mathematics

Faculty of Natural Sciences

For academic year: 2019/20 Last Updated: 20 November 2019

MAT-30001 - Graph Theory

Mathematics Minor (Level 6)

None

None

None

This module introduces the concept of a graph as a pictorial representation of a symmetric relation. A variety of topics are investigated and, for each one, at least one of the major theorems is proved. The emphasis is on pure graph theory although a significant number of applications are explored via worked examples and coursework.

The module develops the following Keele Graduate attributes:

1. An open and questioning approach to ideas, demonstrating curiosity and independence of thought.

2. An appreciation of the development and value of Mathematics and the links between different areas of the subject.

4. The ability creatively to solve problems using a range of different approaches and techniques, and to determine which techniques are appropriate for the problem at hand.

6. The ability to communicate clearly and effectively in written form.

The module develops the following Keele Graduate attributes:

1. An open and questioning approach to ideas, demonstrating curiosity and independence of thought.

2. An appreciation of the development and value of Mathematics and the links between different areas of the subject.

4. The ability creatively to solve problems using a range of different approaches and techniques, and to determine which techniques are appropriate for the problem at hand.

6. The ability to communicate clearly and effectively in written form.

The aim of this module is to study various topics in graph theory, together with a number of applications.

recognise, and establish properties, of different types of graphs such as trees, bipartite and complete graphs: 1,2

prove, and apply, conditions for a graph to be Eulerian or Hamiltonian: 1,2

prove, and apply, results related to the colouring of the vertices or edges of a graph: 1,2

prove, and apply, results related to properties of extremal graphs: 1,2

prove, and apply, results concerning planar graphs: 1,2

prove, and apply, conditions for a graph to be Eulerian or Hamiltonian: 1,2

prove, and apply, results related to the colouring of the vertices or edges of a graph: 1,2

prove, and apply, results related to properties of extremal graphs: 1,2

prove, and apply, results concerning planar graphs: 1,2

Lectures: 30 hours

Preparation of coursework: 30 hours

Independent study: 88 hours

Unseen examination : 2 hours

Preparation of coursework: 30 hours

Independent study: 88 hours

Unseen examination : 2 hours

None

PROBLEM SOLVING

Continuous assessment will consist of two equally weighted Class Tests of approximately 60 minutes.

2 HOUR UNSEEN EXAM

The examination paper will consist of no less than five and not more than eight questions all of which are compulsory.