Graph theory is the study of connections.

Let's say you have a collection of items. What sort of items you ask? The items can be anything. They could be as concrete as a group of students in a classroom or as abstract as the atoms in a complicated molecule. They can be close to home like the intersections in your neighbourhood or as far flung as individual computers connected to the Internet. Some of these items will have connections between them and others won't. Kids in a classroom are connected by their friendships. Atoms are connected by chemical bonds. Intersections are connected by roads. Computers are connected by phone lines. In each example some items were connected and others weren't. Graph theory is the study of these connections.

At this point you could reasonably ask how we're going to handle such a wide variety of situations without getting bogged down in an endless list of special cases. This is where the magic of mathematical modeling comes to the rescue. We won't talk about friends or intersections but "vertices". What's a vertex? Physically it will be a dot on a piece of paper, connected to other dots by segments. The dots can be atoms or computers; the segments can be chemical bonds or phone lines. You'll see as we go along that the theory applies no matter what you let the dots and segments represent.

Classroom Format and Style

I have two goals for this series of lessons. First, I want to present a technically sound introduction to graph theory. Second, I want you ot understand what I'm talking about. To achieve these goals, I'm going to present the core ideas in two different versions, side by side. One version will be in the technically correct language of mathematics. The other will be an "English translation". I encourage you not to ignore the mathematical version. Read that side first and then read the English version. If you compare the two point by point I hope you'll find that the mathematical language isn't nearly as impenetrable as you might have thought.

Links that are in an olive green are "definition links". when you click on one a pop-up window will appear that gives the definition or some additional information about the item, similar to a footnote in a paper book.

Java Issues
Many of the sections in this class use Java applets to provide interactive areas where you can experiment with the ideas discussed in the text. To use these applets you need to have at least version 1.5 of Sun's Java run time. If you're not sure if you have it or not, go to this page on Sun's website and click on the "Verify Installation" button. This will get the version your browser is currently using and give you a link to download the latest version if you don't already have it.
"In the Real World"
Throughout the class, you'll see sections labeled "In the Real World". These areas are projects where you can get out of your chair and use what we've been talking about based on your own neighborhood and communmity.