| Lecture Number |
Date |
Sections in Text |
Brief Description |
| 1 |
Monday, 3/30 |
1.1 |
Introduction, Fundamental Definitions and Examples |
| 2 |
Wednesday, 4/1 |
1.1 - 1.2 |
Isomorphisms, Paths, Connected Graphs |
| 3 |
Friday, 4/3 |
1.2 |
Cut-edges, Bipartite Graphs, Eulerian Circuits |
| 4 |
Monday, 4/6 |
1.2 - 1.3 |
Eulerian Circuits, Extremal Problems |
| 5 |
Wednesday, 4/8 |
1.3 |
Extremal Problems, Graphic Sequences |
| 6 |
Friday, 4/10 |
1.4 |
Directed Graphs, Tournaments |
| 7 |
Monday, 4/13 |
2.1 |
Equivalent Definitions of Trees, Spanning Trees |
| 8 |
Wednesday, 4/15 |
2.1 - 2.2 |
Distance in Graphs, Centers of Trees, Prufer Codes |
| 9 |
Friday, 4/17 |
2.2 |
Cayley's Formula, Counting the Number of Spanning Trees |
| 10 |
Monday, 4/20 |
2.3 |
Minimum Weight Spanning Trees, Kruskal's Algorithm |
| 11 |
Wednesday, 4/22 |
2.3 - 3.1 |
Dijkstra's Algorithm, Matchings |
| 12 |
Friday, 4/24 |
3.1 |
Augmenting Paths, Hall's Condition |
| 13 |
Monday, 4/27 |
- |
First Exam |
| 14 |
Wednesday, 4/29 |
3.1 |
Vertex Covers, Bipartite Graph Results |
| 15 |
Friday, 5/1 |
3.1, 4.1 |
Matchings vs. Edge Covers, Stable Matchings, Connectivity |
| 16 |
Monday, 5/4 |
4.1 |
Connectively, Edge-Connectivity |
| 17 |
Wednesday, 5/6 |
4.2 |
Internally Disjoint Paths, 2-Connectedness, Menger's Theorem |
| 18 |
Friday, 5/8 |
4.2, 4.3 |
Menger's Theorem, Max-Flow Min-Cut Theorem (without proofs) |
| 19 |
Monday, 5/11 |
5.1 |
Vertex Coloring, Simple Bounds, Joins and Cartesian Products |
| 20 |
Wednesday, 5/13 |
5.1 |
Greedy Colorings, Brooks' Theorem |
| 21 |
Friday, 5/15 |
5.2 |
Mycielski's Construction, Turan Graphs |
| 22 |
Monday, 5/18 |
6.1 |
Planar Graphs, Euler's Formula |
| 23 |
Wednesday, 5/20 |
6.2 |
Kuratowski's Theorem, Five-Color Theorem, Four-Color Theorem |
| 24 |
Friday, 5/22 |
8.3 |
Ramsey Theory |
| - |
Monday, 5/25 |
- |
No Class (Memorial Day) |
| 25 |
Wednesday, 5/27 |
8.3 |
Ramsey Theory, Bounding Ramsey Numbers |
| 26 |
Friday, 5/29 |
- |
Random Graphs |
| 27 |
Monday, 6/1 |
- |
Random Graphs, Limit Laws |