Instructor: Nadia Lafrenière
Course on Canvas: https://canvas.dartmouth.edu/courses/52242/ ⇗
Syllabus
Sections of the book Brief Description - Course content Week 1 Download Week 1 1.1, 1.2 Day 1: Basic definitions, examples of problems in graph theory. Download Day 1: Basic definitions, examples of problems in graph theory. Day 2: Adjacency and incidence matrices, isomorphisms. Download Day 2: Adjacency and incidence matrices, isomorphisms. Day 3: Paths, walks, cycles, components, cut-edges, cut-vertices, induced subgraphs. Download Day 3: Paths, walks, cycles, components, cut-edges, cut-vertices, induced subgraphs. Week 2 Download Week 2 1.2, 1.3 Day 4: Characterization of bipartite graphs, Eulerian graphs. Download Day 4: Characterization of bipartite graphs, Eulerian graphs. Day 5: Vertex degrees, degree-sum formula, reconstruction conjecture. Download Day 5: Vertex degrees, degree-sum formula, reconstruction conjecture. Day 6: Extremal problems: largest minimum degree in disconnected graphs, largest bipartite subgraph, triangle-free graphs, etc. Download Day 6: Extremal problems: largest minimum degree in disconnected graphs, largest bipartite subgraph, triangle-free graphs, etc. Week 3 Download Week 3 1.3, 1.4, 2.1, 2.2 Day 7: Degree sequences, graphic sequences. Download Day 7: Degree sequences, graphic sequences. Day 8: Directed graphs, connected digraphs, Eulerian digraphs, De Bruijn cycles Download Day 8: Directed graphs, connected digraphs, Eulerian digraphs, De Bruijn cycles(pre-recorded video, no lecture; see announcement). Day 9: Trees and forests, characterizations of trees. Radius and diameter. Spanning trees (notes with blanks Download notes with blanks, complete notes Download complete notes) Week 4 Download Week 4 2.2 Day 10: Enumeration of trees, Cayley’s formula, Prüfer code. (notes with blanks Download notes with blanks, complete notes Download complete notes) Day 11: Counting spanning trees, deletion-contraction (notes with blanks Download notes with blanks, complete notes Download complete notes). Day 12: The matrix tree theorem, graceful labelings (notes with blanks Download notes with blanks, complete notes Download complete notes). End of the content for Midterm. Practice questions for the midterm Download Practice questions for the midterm Week 5 Download Week 5 2.3, 3.1 Day 13: Minimum spanning trees (Kruskal’s algorithm), shortest paths (Dijkstra’s algorithm). (notes with blanks Download notes with blanks, complete notes Download complete notes). Day 14: Matchings, maximal and maximum matchings, M-augmenting paths. Hall's theorem and consequences (notes with blanks Download notes with blanks, complete notes Download complete notes, Numberphile video (Links to an external site.)). x-hour: Midterm (in-class) (exam Download exam, solutions Download solutions) Day 15: Min-max theorems, maximum matchings and vertex covers, independent sets and edge covers (notes Download notes, supplemental proof Download supplemental proof) Week 6 Download Week 6 4.1, 4.2, 4.3 Day 16: Connectivity, vertex cuts, Edge-connectivity, disconnecting sets, Whitney's theorem (notes with blanks Download notes with blanks, complete notes Download complete notes) Day 17: Blocks, k-connected graphs, Menger’s theorem (notes with blanks Download notes with blanks, complete notes Download complete notes) Day 18: Line graphs. Network flow problems, flows and source/sink cuts (notes with blanks Download notes with blanks, complete notes Download complete notes) Week 7 Download Week 7 4.3, 5.1 Day 19: Ford-Fulkerson algorithm. Max-flow min-cut theorem (notes Download notes). Day 20: Graph coloring (notes with blanks Download notes with blanks, complete notes Download complete notes) Day 21: Bounds on chromatic numbers, chromatic numbers of graphs constructed from smaller graphs (notes with blanks Download notes with blanks, complete notes Download complete notes) Week 8 Download Week 8 5.3, 6.1 Day 22: The chromatic polynomial, the deletion-contraction recurrence (notes with blanks Download notes with blanks, complete notes Download complete notes). Day 23: Properties of the chromatic polynomial, simplicial elimination orderings, acyclic orientations. (notes with blanks Download notes with blanks, complete notes Download complete notes) Day 24: Planar graphs, Euler's formula. (notes Download notes) Week 9 Download Week 9 6.2, 6.3 Day 25: Kuratowski's theorem. (complete notes Download complete notes, notes with blanks Download notes with blanks) Day 26: Five and four color theorems. Seven(!) color theorem (notes Download notes). Day 27: Final project presentations Week 10 Monday: No class, Memorial day. Day 28: Final project presentations Week 11 Final project Office hours by appointment. Final project due June 6.