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, cutedges, cutvertices, induced subgraphs. 
Week 2 
1.2, 1.3 
M: Characterization of bipartite graphs, Eulerian graphs, vertex degrees, degreesum formula. W: Reconstruction conjecture. Extremal problems: largest minimum degree in disconnected graphs, largest bipartite subgraph, F: More extremal problems: trianglefree 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 (Xhour): Counting spanning trees, deletioncontraction. 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, Maugmenting paths. Hall's theorem and consequences. Th (Xhour): Quiz 2. F: Minmax 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: Edgeconnectivity, disconnecting sets, Whitney's theorem. F: Blocks, kconnected graphs. 
Week 7 
4.3, 5.1 
M: Menger’s theorem, line graphs. Network flow problems, value of a flow. W: Source/sink cuts. FordFulkerson algorithm. Maxflow mincut theorem. Th (Xhour): 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 deletioncontraction 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 (Xhour): 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. 