Instructor: Sergi Elizalde
Course on canvas.dartmouth.edu.⇗
Syllabus
|
|
Sections |
Brief Description |
|
Week 1 |
1.1, 1.2 |
M: Basic definitions, examples of problems in graph theory. W: Adjacency and incidence matrices, isomorphisms. F: Paths, walks, cycles, components, cut-edges, cut-vertices. |
|
Week 2 |
1.2, 1.3 |
M: Induced subgraphs, characterization of bipartite graphs, Eulerian graphs. W: Vertex degrees, degree-sum formula, reconstruction conjecture. F: Extremal problems: largest minimum degree in disconnected graphs, largest bipartite subgraph. |
|
Week 3 |
1.4 |
M: No class on Apr 8 (Sergi away at a conference). W: Triangle-free graphs. Degree sequences, graphic sequences. Directed graphs. Th (X-hour): Quiz 1. F: Connected digraphs, Eulerian digraphs, De Bruijn cycles. Orientations and tournaments. |
|
Week 4 |
2.1, 2.2 |
M: Trees and forests, characterizations of trees. W: Radius and diameter. Spanning trees. F: Enumeration of trees, Cayley’s formula, Prüfer code. The deletion-contraction formula. |
|
Week 5 |
2.3, 3.1 |
M: The matrix tree theorem. Decompositions and graceful labelings. Minimum spanning trees (Kruskal’s algorithm). W: Shortest paths (Dijkstra’s algorithm), Breadth First Search. Maximal and maximum matchings, M-augmenting paths. Th (X-hour): Quiz 2. F: Hall's theorem and its consequences. |
|
Week 6 |
3.1, 4.1 |
M: Min-max theorems, matchings and vertex covers, independent sets and edge covers. W: Relating maximum matchings, minimum vertex covers, maximum independent sets, and minimum edge covers. Connectivity, vertex cuts. F: Edge-connectivity, disconnecting sets. Whitney's theorem. |
|
Week 7 |
4.2, 4.3 |
M: Blocks, k-connected graphs. W: Menger’s theorem, line graphs. Network flow problems, value of a flow. Th (X-hour): Quiz 3. F: Source/sink cuts. Ford-Fulkerson algorithm. Max-flow min-cut theorem. |
|
Week 8 |
5.1, 5.3 |
M: Graph coloring. Bounds on chromatic numbers, chromatic numbers of graphs constructed from smaller graphs. W: The chromatic polynomial, the deletion-contraction recurrence. F: Properties of the chromatic polynomial, simplicial elimination orderings, acyclic orientations. |
|
Week 9 |
Chapter 6 |
M: Planar graphs, Euler's formula. W: Kuratowski's theorem. Th (X-hour): Quiz 4. F: Five and four color theorems. Final exam handed out. |
|
Week 10 |
Chapter 6 |
(No class on Memorial Day) W: Final exam due. |