Graph Theory and
The goals of this project are, firstly, to
acquaint you with some of the ideas and principles involved in the mathematical
study of counting and combinatorial graphs, and secondly, to provide a starting
point for mathematical explorations of your own.
Course designed by Dale
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
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
. . . 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
. . . 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
As the semester continues, further lessons will appear, including:
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