# Graph Theory

*20 credits / 30 lectures*

Graph Theory is the mathematics of *networks*: collections of things (which we call *vertices* or *nodes* or *points*), between some of which are connections (*edges*). The World Wide Web is a graph. So are the streets of a city, the complex web of interactions that constitutes human society, power stations and the connections between them, and Friends on Facebook. That having been said, this module deals with graphs as abstract mathematical structures and leaves you to pick up the applications on your own. Most of our time is spent covering various theorems and proofs. Possible topics covered include the following:

- Connectivity, vertex and edge cuts, Menger’s Theorem.
- Planar graphs, Kuratowski’s Theorem, the Four and Five Colour Theorems.
- Vertex colouring, Brooks’ Theorem.
- Eulerian and Hamiltonian graphs.
- Graphs and groups, permutation groups and the Cauchy-Frobenius-Burnside Theorem.
- Other topics to be decided.

Prerequisites:

- Some knowledge of group theory is needed for part of the course.
- Students in this module are assumed to be familiar with the following topics from the 3rd year module 3DM (Discrete Mathematics):
- Basics: Graphs and digraphs, degree, isomorphism, operations on graphs,
- Distance in graphs,
- Basic graph structures: bipartite graphs, cut-vertices and bridges,
- Trees.

The above material can be found in this document.

**Contact Us**

**Tel:** +27 21 650 3191

**Email:** tanya.hannival@uct.ac.za

**Physical address:**

Room M3.19

Mathematics Building

University Avenue North

University of Cape Town

Private Bag X3, Rondebosch 7701

South Africa

**Honours Program Convenor**

Dr David Erwin

+27 21 650 3208

david.erwin@uct.ac.za

Room M3.25, Mathematics Building

**Postgraduate Administrator**

Ms Tanya Hannival

+27 21 650 4527

tanya.hannival@uct.ac.za

Room M3.19.3, Mathematics Building