Course on Canvas: https://canvas.dartmouth.edu/courses/52242/

## Syllabus



Sections of the book

Brief Description - Course content

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 3: Paths, walks, cycles, components, cut-edges, cut-vertices, induced subgraphs. Download Day 3: Paths, walks, cycles, components, cut-edges, cut-vertices, induced subgraphs.

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.

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).

2.2

End of the content for Midterm. Practice questions for the midterm Download Practice questions for the midterm

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.)).

4.1, 4.2, 4.3

Day 18: Line graphs. Network flow problems, flows and source/sink cuts (notes with blanks  Download notes with blanks, complete notes  Download complete notes)

4.3, 5.1

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)

5.3, 6.1

Day 23: Properties of the chromatic polynomial, simplicial elimination orderings, acyclic orientations. (notes with blanks  Download notes with blanks, complete notes  Download complete notes)

6.2, 6.3

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.