All homework assignments are turned in on Gradescope. The quizzes are submitted on Canvas. For more information on how to access and submit the quizzes, see the syllabus.
| Week | Monday | Tuesday | Wednesday | Thursday | Friday |
|---|---|---|---|---|---|
| 1 |
Mar 28 | Mar 29 | Mar 30 | Mar 31 | Apr 1 |
| 2 |
Apr 4 | Apr 5 | Apr 6 | Apr 7
Homework 1 due
11:59pm PDT |
Apr 8 |
| 3 |
Apr 11 | Apr 12 | Apr 13 | Apr 14
Homework 2 due
11:59pm PDT |
Apr 15
Quiz 1 (on Canvas)
|
| 4 |
Apr 18 | Apr 19 | Apr 20 | Apr 21
Homework 3 due
11:59pm PDT |
Apr 22 |
| 5 |
Apr 25 | Apr 26 | Apr 27 | Apr 28
Homework 4 due
11:59pm PDT |
Apr 29
Quiz 2 (on Canvas)
|
| 6 |
May 2 | May 3 | May 4 | May 5
No HW due
|
May 6
Midterm (in class)
|
| 7 |
May 9 | May 10 | May 11 | May 12
Homework 5 due
11:59pm PDT |
May 13 |
| 8 |
May 16 | May 17 | May 18 | May 19
Homework 6 due
11:59pm PDT |
May 20 |
| 9 |
May 23 | May 24 | May 25 | May 26
Homework 7 due
11:59pm PDT |
May 27
Quiz 3 (on Canvas)
|
| 10 |
May 30
No class
(Memorial Day) |
May 31 | Jun 1 | Jun 2
Homework 8 due
11:59pm PDT |
Jun 3 |
| Finals |
Jun 6 | Jun 7 | Jun 8 | Jun 9 | Jun 10 |
Here is a tentative schedule of what will be covered in each lecture, together with the relevant section(s) of the book: Introduction to Graph Theory (Course Notes), by Professor Jacques Verstraete. I will fill in the schedule for the remaining lectures throughout the quarter (and update the schedule with any other changes). This is only a rough schedule, and there will likely be some give and take between lectures.
| Week | Date | Topic | Book Sections |
|---|---|---|---|
| 1 | 3/28 | Definition and basic properties of graphs (warm-up, example) | 1,1. 1.4 |
| 3/30 | Basic classes of graphs, and the Handshaking Lemma (warm-up) | 1.3, 1.5, 1.6 | |
| 4/1 | Subgraphs, connected graphs, and walks | 1.7, 2.1, 2.2 | |
| 2 | 4/4 | Eulerian graphs (vocab slide, Eulerian slide) | 2.3, 2.5 |
| 4/6 | Hamiltonian graphs (+ finish Eulerian graphs) Example of Hierholzer's Algorithm) |
2.5 | |
| 4/8 | Finish Hamiltonian graphs | 2.5 | |
| 3 | 4/11 | Bridges and trees (bridges slide, trees slide) | 3.1 |
| 4/13 | Breadth-first search, depth-first search (slide 1, slide 2, slide 3) | 3.1, 3.4 | |
| 4/15 | Characterizing bipartite graphs (warm-up) | 3.2 | |
| 4 | 4/18 | Prim's and Kruskal's Algorithms (warm-up) | 3.5 |
| 4/20 | Dijkstra's Algorithm (Prim slide, Dijkstra slide, Dijkstra proof, Dijkstra video) |
3.6 | |
| 4/22 | Independent sets and covers (warm-up) | 5.1 | |
| 5 | 4/25 | Hall's Theorem | 5.2 |
| 4/27 | Systems of distinct representatives | 5.3 | |
| 4/29 | Intro to coloring, degenrate graphs (warm-up, vocab) | 6.4 | |
| 6 | 5/2 | Brooks' Theorem, scheduling problems (warm-up) | 6.3, 6.5 |
| 5/4 | Midterm Review | ||
| 5/6 | Midterm | ||
| 7 | 5/9 | Konig's Theorem (warm-up, vocab, coloring slide) | 6.1 |
| 5/11 | Euler's formula (warm-up, vocab) | 7.1 | |
| 5/13 | Coloring planar graphs (warm-up, slides) | 7.3 | |
| 8 | 5/16 | Flows and Capacities (warm-up) | 8.1, 8.2 |
| 5/18 | Cuts (warm-up) | 8.3 | |
| 5/20 | The Max-Flow Min-Cut Algorithm (warm-up, Ford-Fulkerson Algorithm example) |
8.4 | |
| 9 | 5/23 | Proof of Hall's Theorem using Max-Flow Min-Cut (warm-up) | 8.5 |
| 5/25 | Vertex and Edge Connectivity (warm-up) | 4.6 | |
| 5/27 | Proof of Menger's Theorems (warm-up, paths slide, notes on proof of Menger's Theorem) |
8.6 | |
| 10 | 5/30 | No Class (Memorial Day) | |
| 6/1 | Fun problems :) (warm-up) | ||
| 6/3 | |||
| 6/10 | Final Exam (Friday of finals week, 7-10pm) |