I.2. Circuits, trees, and shaking hands (or, How to cross a bridge).
The relationship between degrees and the number of edges. Euler's solution to the Konigsberg bridge problem.
I.3. The short way, the long way, and the best way.
From a given location in a city, how do you find the shortest route to every other place in the city? We present breadth first and depth first search algorithms and applications.
I.4. Building communications networks cheaply.
Given a set of possible edges with costs associated with constructing each of them, how do we determine which of them to build to create a connected graph at the cheapest cost?
I.5. Delivering the goods.
Given a network of pipes, what is the maximum amount of water that can flow from the reservoir to the city? An algorithm for max flows and the minimum cut condition are given.
I.6. The Tour de DREI.
A cycle that visits each vertex in the graph exactly once is called a hamilton cycle. We look at some simple conditions under which G has a hamilton cycle.
I.7. If you want to find a prince you have to kiss a lot of toads.
Given an equal number of men and women, can you pair them up so that they are all reasonably happy? The mathematical definition of a stable marriage.
I.8. Graphs undercover.
A cycle that visits each vertex in the graph exactly once is called a hamilton cycle. We look at some simple conditions under which G has a hamilton cycle.
I.9. Water, water everywhere.
In a graph with pipes for edges, can we fill the pipes with water and keep the water moving so that there is no standing water anywhere? Nowhere zero flows and their relationship to cycle covers and coloring.
II.2. The many faces of a graph.
Euler's formula for planar graphs and induction. The connection between average degree and chromatic number.
II.3. Why mathematicians can't distinguish coffee cups from doughnuts.
What's a torus? On what surfaces can a graph be drawn with no crossings? Credit Harley Davidson for helping us teach this class.
II.4. The five color theorem.
Okay, it looks like we're getting better at this. We use induction, and a recoloring argument if necessary, to color planar graphs.
II.5. Graphs of minor importance.
How can one tell if a graph is planar or not? Kuratowski and Wagner teach us somewhat local, somewhat global properties to watch out for.
II.6. More graph theory for minors.
A recursive algorithm for drawing a graph in the plane.
II.7. Painting planes.
Is it possible to draw a graph so that all its edges have the same length? Unit distance graphs and applications to the chromatic number of 172
II.8. Make the call.
How can we ensure that a telephone call will still go through, even if many routing stations accidentally shut down? The number of disjoint routes from one vertex to another is a critical parameter.
II.9. When max is less than min.
The connectivity results of Whitney and Menger.
III.2. Coloring the edges - a big difference!
Since coloring the edges of a graph is like coloring the vertices of its line graph, the edge coloring problem is a special case of the vertex coloring problem, and so it should be an easier problem. It is and it isn't. Vizing's theorem answers one question and raises another.
III.3. All graphs have class.
If at first you don't succeed . .. recolor! Unlocking the key to Vizing's theorem.
III.4. Why BIC makes a 4-color pen.
The most famous graph theory problem, now a theorem after a century of incorrect "proofs", and the first proof of a major theorem in which a computer played a central role. The four color theorem and its many disguises.
III.5. How to choose a graph
Usually each vertex must be colored from the set {1, 2, . . ., k}. If we allow each vertex to be colored from its own set of size k, is the problem harder or easier?
III.6. List coloring planar graphs an easier proof of a harder theorem.
List coloring and choosing are synonymous. we 1nvestlgate planar graphs, outer
planar graphs, triangle free graphs, planar graphs, and more.
III.7. Some graphs are perfect.
Lesson 1 concentrated on the upper bound to chromatic number. Now it's time to consider for which graphs the lower bound of its clique number is tight. For some graphs the clique and chromatic numbers identical for each of its subgraphs Sounds perfect to me.
III.8. Equivalent problems in disguise.
Tying together the three themes of DREI '98 - cycles, embeddings, and colorings.
III.9. Can I change my mind?
Not for on - line chromatic number. You receive vertices one at a time and color each one immediately, without seeing the rest of the graph yet. For many applications, it is the only way a computer can color a graph.