| 1 |
Aug 18 |
Introduction; Definitions |
1.1 |
HW1 assigned. |
| 2 |
Aug 23 |
Graph isomorphisms; more definitions |
1.1 |
- |
| 3 |
Aug 25 |
Petersen Graph; Walks, Trails, and Paths |
1.1, 1.2 |
- |
| 4 |
Aug 30 |
Induction; cycles in walks; induced subgraphs |
1.2 |
- |
| 5 |
Sep 1 |
Bipartite characterization; Eulerian circuits |
1.2 |
- |
| 6 |
Sep 6 |
Decomposition into trails; Hypercubes |
1.3 |
HW1 due; HW2 assigned. |
| 7 |
Sep 8 |
Algorithmic proofs (max-cut); Turan numbers; Mantel's Theorem |
1.3 |
- |
| 8 |
Sep 13 |
Induction trap; degree sequences, Havel--Hakimi |
1.3 |
- |
| 9 |
Sep 15 |
Directed graphs; orientations; de sBruijn cycles |
1.4 |
- |
| 10 |
Sep 20 |
Tournaments; Trees; Bridge-it |
1.4,2.1 |
HW2 due; HW3 assigned. |
| 11 |
Sep 22 |
Enumerating spanning trees; Deletion-contraction; Matrix Tree Thm |
2.2 |
HW2 due; HW3 assigned. |
| 12 |
Sep 27 |
Matchings; Augmenting paths |
3.1 |
- |
| 13 |
Sep 29 |
Hall's Theorem |
3.1 |
- |
| 14 |
Oct 4 |
Konig--Egervary |
3.1 |
HW3 due; HW4 assigned. |
| 15 |
Oct 6 |
Midterm Exam (coverage up to and including Sept. 29) |
- |
- |
| 16 |
Oct 11 |
Matchings in non-bipartite graphs; Tutte's Theorem |
3.3 |
- |
| 17 |
Oct 13 |
Tutte's Theorem: Applications |
3.3 |
- |
| 18 |
Oct 18 |
Vertex connectivity; Harary graphs |
4.1 |
HW4 due; HW5 assigned. |
| 19 |
Oct 20 |
Edge connectivity; bonds |
4.1 |
- |
| 20 |
Oct 25 |
Block decompositions; the block-cutpoint graph |
4.1 |
- |
| 21 |
Oct 27 |
2-connected graphs; ear decompositions |
4.2 |
- |
| 22 |
Nov 1 |
Closed Ear Decomposition; Menger's Theorem |
4.2 |
- |
| 23 |
Nov 3 |
Network Flows I: Definitions, Augmenting paths |
4.3 |
HW5 due; HW6 assigned. |
| 24 |
Nov 8 |
Network Flows II: Ford--Fulkerson; max-flow/min-cut theorem |
4.3 |
- |
| 25 |
Nov 10 |
Network Flows III: integrality and applications |
4.1 |
- |
| 26 |
Nov 15 |
Chromatic number: definitions, k-partite graphs, elementary lower bounds |
4.3 |
- |
| 27 |
Nov 17 |
Chromatic number: cartesian products, greedy algorithm |
5.1 |
HW6 due; HW7 assigned (Nov 23). |
| 28 |
Nov 29 |
Brooks's Thm; Mycielski's construction |
5.1-5.2 |
- |
| 29 |
Dec 2 |
Turan's Thm; Hajos and Hadwiger conjectures |
5.2 |
- |
| 30 |
Dec 6 |
Planar Graphs; Kuratowski's Thm; Euler's formula; 4-color theorem |
6.1-6.3 |
HW7 due |
| - |
Dec 13 |
Final Exam: 5pm to 7pm |
- |
HW7 late deadline |