Instructor: Nadia Lafrenière
Course on Canvas: https://canvas.dartmouth.edu/courses/46201 ⇗
Syllabus
|
|
Sections of the book |
Brief Description - Pre-recoded 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, cut-edges, cut-vertices, induced subgraphs. Day 5: Characterization of bipartite graphs, Eulerian graphs. Day 6: Vertex degrees, degree-sum 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, triangle-free 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, deletion-contraction. |
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, M-augmenting 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: Min-max 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: Edge-connectivity, 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, k-connected graphs, Menger’s theorem. Day 20: Line graphs. Network flow problems, flows and source/sink cuts. Day 21: Ford-Fulkerson algorithm. Max-flow min-cut 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 deletion-contraction 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. |
|