Graph Theory and Enumeration
Course designed by Dale Winter

The theory of graphs started in a paper published in 1736 by the Swiss mathematician Leonhard Euler. The idea in Euler's paper, which has blossomed into graph theory, grew out of a now popular problem known as the "Seven Bridges of Königsberg." The problem goes something like this:

During the eighteenth century the city of Königsberg (in East Prussia) was divided into four sections (including the island of Kneiphof) by the Pregel river. Seven bridges connected these regions, as shown in the picture below.

It was said that people spent their Sundays walking around, trying to find a starting point so that they could walk about the city, cross each bridge exactly once, and then return to their starting point. Can you find a starting point, and a path around the city that allow you to do this?

Another famous problem that we will develop tools to help us with is the "Four Color Problem." This problem can be stated very concisely:

What is the smallest number of colors needed to color any planar map so that any two neighboring regions have different colors?

Over the last 150 years, some big shots in the world of mathematics have been involved with this problem. Around 1850, Francis Guthrie (1831-1899) showed how to color a map of all the counties in England using only four colors. He became interested in the general problem, and talked about it with his brother, Frederick. Frederick talked about it with his math teacher, Augustus DeMorgan (you might have heard of DeMorgan's laws in logic and proof), who sent the problem to William Hamilton (for whom Hamiltonian mechanics is named). Hamilton was evidently too interested in other things to work on the four color problem, and it lay dormant for about 25 years. In 1878, Arthur Cayley made the scientific community aware of the problem again, and shortly thereafter, British mathematician Sir Alfred Kempe devised a 'proof' that was unquestioned for over ten years. However, in 1890, another British mathematician, Percy John Heawood, found a mistake in Kempe's work. The problem remained unsolved until 1976, when Kenneth Appel and Wolfgang Haken produced a proof involving an intricate computer analysis of 1936 different configurations.

Some mathematicians have expressed dissatisfaction with Appel's and Haken's proof. There is still no 'cute' proof of the four color problem. Although it is unlikely that we will delve into the intricacies of Appel's and Haken's actual proof, we will study how to represent a map coloring using combinatorial graphs, and solve the "Five Color Problem" which is a bit easier.

In the graph theory part of this course, we will study mathematical concepts that will help us to solve this problem, and which have many useful applications elsewhere.

Littered across the web pages are opportunities for you to think deeply about the mathematics described. Some of the questions on the web site may seem to be very ambiguous. The questions are intended to be very open-ended, so that you have a lot of freedom to create math for yourself.

The opportunities are indicated with banners. When you see ...

. . . feel free to pause and think about the material you have just been studying. Often there is more to the material than first meets the eye. You are welcomed and encouraged to talk with your colleagues.

. . . feel free to use a calculator or computer to investigate further aspects of the mathematics that you have been studying. Again, you are very welcome to talk about your investigations with others.

. . . look for links to other web sites that treat similar material. A Java compatible browser is recommended, as many of the graph-related web sites feature interactive Java applets that allow you to investigate the math over the web.

Content of the Course

The subject matter of this course is the mathematical study of combinatorial graphs and methods of enumeration.

Contents

We will also study some techniques of counting, or enumeration:
Lesson 7: Counting Arrangements.
Lesson 8: Counting Selections.
Lesson 9: Venn Diagrams.
Lesson 10: The Pigeon Hole Principle.
Lesson 11: The Inclusion-Exclusion Principle.
Lesson 12: Generating Functions.
Lesson 13: Burnside's Lemma.

Special Credits Much of the subject matter presented in this web course was taught to me by Melissa White and Marston Conder of the University of Auckland. I have drawn on their excellent class notes while preparing these lessons.



Return to MMSS Main Page