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 |