Graph Theory


Graph theory is the study of adjacency. Not any specific kind of adjacency, but the abstracted idea of adjacency. If one is in a car, places are "adjacent" if they are connected by a roadway. If one is in an airport, cities are "adjacent" if there is a flight from one to another. If one is solving a puzzle, positions are "adjacent" if you can shift just one part of the puzzle to get from one to the other. These situations may seem different, but in all of them the question of how to most quickly (or cheaply, or what have you) get from one place, city, or position to another (and whether it is possible at all) can be answered in fundamentally the same way. Graph theory captures this idea of things being "adjacent" to one another in abstract, mathematical terms, and studies it without the hindrances of useless specifics.

Links to the problem sets on this page will be available gradually corresponding to the course schedule.

Graph Theory : Bridges, circuits, trees and maps

Part 1. Graphs, degrees, trees, hydrocarbon molecules, Chinese postman problem, Bacon numbers.

Part 2. Flow, Street Network, Avoiding Conflicts, Coloring Trees, Complete Graphs, Coloring Polygons, Plato and Euler, map-coloring problem.