Chapter 5: Graph Theory

Graph Theory is a relatively new area of mathematics, first studied by the super famous mathematician Leonhard Euler in 1735. Since then it has blossomed in to a powerful tool used in nearly every branch of science and is currently an active area of mathematics research.

The problem above, known as the Seven Bridges of Königsberg, is the problem that originally inspired graph theory. Consider a “different” problem: Below is a drawing of four dots connected by some lines. Is it possible to trace over each line once and only once (without lifting up your pencil, starting and ending on a dot)?

There is an obvious connection between these two problems. Any path in the dot and line drawing corresponds exactly to a path over the bridges of Königsberg.

Pictures like the dot and line drawing are called graphs. Graphs are made up of a collection of dots called vertices and lines connecting those dots called edges. When two vertices are connected by an edge, we say they are adjacent. The nice thing about looking at graphs instead of pictures of rivers, islands and bridges is that we now have a mathematical object to study. We have distilled the “important” parts of the bridge picture for the purposes of the problem. It does not matter how big the islands are, what the bridges are made out of, if the river contains alligators, etc. All that matters is which land masses are connected to which other land masses, and how many times.

We will return to the question of finding paths through graphs later. But first, here are a few other situations you can represent with graphs: