The exams will be somewhat unusual in that I will reserve a lot of time for them, like 3-4 hours each, so as to give you plenty of time to do it. I don't want give a take-home exam with such a big class but on the other hand I don't want there to be time pressure on the exams.

and collect it the following Tuesday. No late HW.

Click here for the assignments.

- Kruskal's spanning tree algorithm
- Divide and Conquer algorithms
- Trees in action: cut locus, farey graph, p-adic numbers
- Prufer codes
- Cauchy-Binet Theorem
- The Matrix Tree Theorem

- Sperner's Lemma
- Eulerian Circuits
- polygonal Jordan curve theorem
- Euler Characteristic
- Dual graphs
- graphs on surfaces
- Kuratowski's Theorem

- 5-Color Theorem
- The Ramsey Theorem
- chromatic number of a graph
- Brooks' Theorem
- The Chromatic Polynomial
- Perfect and Maximum Matchings
- Hall's Marriage Theorem

- Graph Automorphisms and Cayley Graphs
- Quasi-Isometries
- Congruence subgroups and platonic solids
- some infinite graphs: coarse hyperbolic plane, HEIS, SOL
- Conway's Tribones Theorem

- random countable graphs; the Rado graph
- Random Walks on Graphs
- Harmonic Functions
- Electric Networks
- Polya's Recurrence and Transience Theorems

- Max Flow Min Cut
- matroids
- circle packings
- Frieze patterns
- mechanical linkages
- Kastelyn's Formula for perfect matchings