Instructor: Nadia Lafrenière
Course on Canvas: https://canvas.dartmouth.edu/courses/46201 ⇗
Syllabus

Sections of the book 
Brief Description  Prerecoded videos 
Brief Description  Class time 
Week 1 
1.1 
Day 1: Motivating example Day 2: Basic definitions, examples of problems in graph theory. Day 3: Adjacency and incidence matrices, isomorphisms. 
Day 1: Virtual tour of the class and tools, motivating example. Day 2: First examples of proofs. Day 3: Office hours 
Week 2 
1.2, 1.3 
Day 4: Paths, walks, cycles, components, cutedges, cutvertices, induced subgraphs. Day 5: Characterization of bipartite graphs, Eulerian graphs. Day 6: Vertex degrees, degreesum formula, reconstruction conjecture. 
Day 4: Day 1 of study groups! Day 5: Arguments for counting Day 6: Office hours 
Week 3 
1.3, 1.4 
Day 7: Extremal problems: largest minimum degree in disconnected graphs, largest bipartite subgraph, trianglefree graphs, etc. Day 8: Degree sequences, graphic sequences, directed graphs. Day 9: Connected digraphs, Eulerian digraphs, De Bruijn cycles. 
Day 7: Study groups! Day 8: Questions on homework Day 9: Office hours 
Week 4 
2.1, 2.2 
Day 10: Orientations and tournaments. Trees and forests, characterizations of trees. Radius and diameter. Spanning trees. Day 11: Enumeration of trees, Cayley’s formula, Prüfer code. Day 12: Counting spanning trees, deletioncontraction. 
Day 10: Study groups! Day 11: Questions on homework Day 12: Office hours 
Week 5 
2.3, 3.1 
Day 13: The matrix tree theorem, graceful labelings. Day 14: Minimum spanning trees (Kruskal’s algorithm), shortest paths (Dijkstra’s algorithm). Day 15: Matchings, maximal and maximum matchings, Maugmenting paths. Hall's theorem and consequences. 
Day 13: Study groups! Day 14: Questions on homework Day 15: Office hours 
Week 6 
3.1, 4.1 
Day 16: Minmax theorems, maximum matchings and vertex covers, independent sets and edge covers. Midterm Due (we'll discuss the day). Day 17: Independent sets and edge covers (continued). Connectivity, vertex cuts. Day 18: Edgeconnectivity, disconnecting sets, Whitney's theorem. 
Day 16: Study groups! Day 17: Questions on homework Day 18: Office hours 
Week 7 
4.2, 4.3 
Day 19: Blocks, kconnected graphs, Menger’s theorem. Day 20: Line graphs. Network flow problems, flows and source/sink cuts. Day 21: FordFulkerson algorithm. Maxflow mincut theorem. 
Day 19: Study groups! Day 20: Questions on homework Day 21: Office hours 
Week 8 
5.1, 5.3 
Day 22: Graph coloring. Day 23: Bounds on chromatic numbers, chromatic numbers of graphs constructed from smaller graphs. Day 24: The chromatic polynomial, the deletioncontraction recurrence. 
Day 22: Study groups! Day 23: Questions on homework Day 24: Office hours 
Week 9 
5.3, Chapter 6 
Day 25: Properties of the chromatic polynomial, simplicial elimination orderings, acyclic orientations. Day 26: Planar graphs, Euler's formula. Day 27: Kuratowski's theorem. 
Day 25: Study groups! Day 26: Questions on homework Day 27: Study groups! (since there is no class on Monday) 
Week 10 
Chapter 6 
Monday: No class, Memorial day. Day 28: Five and four color theorems. 
Monday: No class, no office hours. Memorial day. Day 28: Seven(!) color theorem. Last day of class 
Week 11 
Final project 
Office hours by appointment. Final project due June 7. 
