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.