You may want to download the lecture slides that were used for these videos (PDF).
1. Planar Graphs
This video defines planar graphs and introduces some of the questions related to them that we will explore. (4:38)
2. Euler’s Formula
This video introduces the concept of a face, and gives Euler’s formula, n – q + f = 1 + t. We will eventually prove this formula. (5:06)
3. Bridges & 2-Connected Graphs
To prove Euler’s formula, we need the idea of a bridge. This video defines a bridge and 2-connected graphs. (2:13)
4. Proof of Euler’s Formula – Part 1
We will prove Euler’s formula using induction. We will consider two cases, the first case is completed in this video. The rest of the proof is in the video that follows. (7:32)
5. Case 2, G Has No Bridges
To complete our proof of Euler’s formula, we consider the case when G has no bridges. (5:25)
6. The Maximum Number of Edges in Planar Graphs
If G is a planar graph with n ≥ 3 vertices and q edges, then q ≤ 3n – 6. This video introduces and discusses this theorem, which we will prove in later videos. (1:25)
7. Setup to prove q ≤ 3n – 6
This video sets up our proof that q ≤ 3n – 6. (4:31)
8. Proof of q ≤ 3n – 6
This video gives our proof that q ≤ 3n – 6. (10:21)
9. The Four Color Theorem
In this video we introduce the mathematics and history behind the famous four-color theorem for a planar graph. We also define a homeomorph of a graph, and discuss its relation to planarity. (6:12)