Instructors: Sergi Elizalde

Course on canvas.dartmouth.edu.

## Syllabus

The slides that I use in class will be posted here as the course progresses, and they have a more accurate description of what has been covered in each class.

 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, induced subgraphs. Week 2 1.2, 1.3 M: Characterization of bipartite graphs, Eulerian graphs, vertex degrees, degree-sum formula. W: Reconstruction conjecture. Extremal problems: largest minimum degree in disconnected graphs, largest bipartite subgraph, F: More extremal problems: triangle-free graphs. Degree sequences, graphic sequences. Week 3 1.4 M: Directed graphs. Connected digraphs, Eulerian digraphs, De Bruijn cycles. Orientations and tournaments. W: Quiz 1. F: No class on Apr 14  (Sergi away at a conference). Week 4 2.1, 2.2 M: Trees and forests, characterizations of trees. Radius and diameter. W:  Spanning trees, Enumeration of trees, Cayley’s formula, Prüfer code. Th (X-hour): Counting spanning trees, deletion-contraction. F: The matrix tree theorem. Decompositions and graceful labelings. Minimum spanning trees (Kruskal’s algorithm). Week 5 2.3, 3.1 M: Shortest paths (Dijkstra’s algorithm), Breadth First Search. Matchings. W: Maximal and maximum matchings, M-augmenting paths. Hall's theorem and consequences. Th (X-hour): Quiz 2. F: Min-max theorems, matchings and vertex covers,  independent sets and edge covers. Week 6 3.1, 4.1, 4.2 M: Relating maximum matchings, minimum vertex covers, maximum independent sets, and minimum edge covers. Connectivity, vertex cuts. W: Edge-connectivity, disconnecting sets, Whitney's theorem.  F: Blocks, k-connected graphs. Week 7 4.3, 5.1 M: Menger’s theorem, line graphs. Network flow problems, value of a flow. W: Source/sink cuts. Ford-Fulkerson algorithm. Max-flow min-cut theorem. Th (X-hour): Quiz 3. F: Graph coloring. Week 8 5.1, 5.3 M: 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.