Date  Chapter  Description 

Jan 13  4.1  Introduction 
Jan 15  3.1  Counting functions between finite sets 
Jan 17  3.1  3.2  Counting injections between finite sets (permutations) 

Jan 20   Martin Luther King Day! (no class) 
Jan 22  3.3  Counting subsets 
Jan 24  3.3  the Binomial Theorem, the Freshman's Dream Identity 

Jan 27  3.3  Mississippi reorderings, poker hands 
Jan 29  3.7  InclusionExclusion 
Jan 31  3.8  Derangements: the Hatcheck Problem 

Feb 3  4.1  Graph basics: examples and isomorphisms 
Feb 5  4.1  (Complete) bipartite graphs, the number of graphs on n vertices 
Feb 7  4.2  Subgraphs and induced subgraphs 

Feb 10  4.2  Walks and the adjacency matrix 
Feb 12   Snow Day 
Feb 14  4.3  Degrees and the degree sequence 

Feb 17  4.3  The Handshake Lemma; Bridges of Königsberg 
Feb 19  Exam 1 
Feb 21  4.4  Eulerian tours 

Feb 24  4.4  proof of the Eulerian Tour Theorem 
Feb 26  4.6  2connected graphs, examples and terminology 
Feb 28  4.6  Cycle characterization of 2connected graphs 

Mar 3  4.6  Ear decompositions of 2connected graphs 
Mar 5  4.7  Extremal problems example: cyclefree graphs 
Mar 7   Automorphisms of the Petersen graph (guest lecturer: Ted Dobson) 

Mar 10   Spring Break! (no class) 
Mar 12   Spring Break! (no class) 
Mar 14   Spring Break! (no class) 

Mar 17  4.7  Maximum # edges in a trianglefree graph 
Mar 19  5.1  Introduction to trees, TFAE 
Mar 21  5.1  The Tree Characterization Theorem 

Mar 24  (5.2)  A brief introduction to computational complexity 
Mar 26  5.3  Spanning trees, Algorithm 1 
Mar 28  5.3  Running time of Algorithm 1 

Mar 31  5.3  Algorithm 2: growing a spanning tree 
Apr 2  5.4  Minimum spanning trees 
Apr 4  5.4  6.1  Matroid Lemma for cyclefree graphs; begin planar graphs 

Apr 7  6.1  Arcs, R^{2}drawings, and R^{2}embeddings 
Apr 9  Exam 2 
Apr 11  6.1  exam solutions, a zoo of surfaces 

Apr 14  6.1  6.2  Stereographic projections, arcconnected regions, faces 
Apr 16  6.2  The Jordan Curve Theorem, K_{5} is not planar 
Apr 18   Religious holiday! (no class) 

Apr 21  6.2  Faces of 2connected graphs, Kuratowski's Theorem 
Apr 23  6.3  Euler's formula for planar graphs 
Apr 25  6.3  Upper bound for # edges of a planar graph, dual graphs 

Apr 28  6.4  kcolorings and the chromatic number 
Apr 30  6.4  The 5color Theorem 

May 8  Final exam (12:00  3:00pm) 