Stuff you should know for the final exam

Enumeration (roughly 1/3 of the exam):
- elementary counting (permutations, combinations)
- the binomial theorem (statement only)
- how to use formal power series
- linear recurrences
- framework for using generating series to solve enumeration problems
- sum & product lemmas & other basic properties (+ proofs)
- weight preserving bijections
- standard types of examples:
   - catalan numbers
   - compositions
   - partitions
   - strings (including decompositions, excluded substring techniques)
- generalizations to multivariate generating series

Graph theory (roughly 2/3 of the exam):
- all definitions
- Basics:
   - standard examples/types of graphs
   - isomorphisms
   - handshake theorem (+ proof)
   - basic facts about walks, paths, cycles, subgraphs, components, etc.
   - relationship between bridges & cycles (+ proofs)
- Trees & applications:
   - basic tree theorems: number of edges, degrees of vertices (+ proofs)
   - a graph is connected iff it has a spanning tree (+ proof)
   - BFST Algorithm
   - fundamental property of BFSTs (statement only)
   - applications of BFSTs: connectedness, shortest paths, girth, bipartite
       graphs (+ proofs)
- Planarity:
   - key difference between bridges & non-bridges (statement only)
   - handshake theorem for faces (+ proof)
   - Euler's formula (+ proof)
   - relationship between degrees of faces and girth (statement only)
   - bound on the number of edges in a planar graph (+ proof)
   - how to prove a wide variety of things using the above
   - Kuratowski's Theorem & Wagner's Theorem (statements only)
- Colouring:
   - 6 colour theorem & variations (+ proof)
   - Existence of the chromatic polynomial
- Matchings
   - what to do with an augmenting paths (+ proof)
   - relationship between covers and matchings (+ proof)
   - Koenig's theorem (statement only)
   - Bipartite Matching Algorithm
   - Hall's theorem (statement only)
   - perfect matchings in regular bipartite graphs (+ proof)

Stuff that we talked about that won't be on the final exam

- combinatorial or algebraic proofs of identities
- proving that strings are "uniquely created"
- stirling numbers
- the matrix transfer method (this is name for the method in Asst. 4, #4)
- enumeration of trees
- eigenvalues of the adjacency matrix
- proof of the 5 colour theorem
- matrix tree theorem