Instructor: Danny Krashen, daniel.krashen@gmail.com Office Hours: Wed 11-12/ Mon 2:30-3:30 (via WebEx)

References

- A first course in graph theory, by Chartrand & Zhang
- Graph Theory with Applications, by Bondy & Murty
- (Incomplete) Graph Theory Notes, by Danny Krashen

Topical lecture outline

- Introduction, examples
- Basic terminology, isomorphism, trails, paths, circuits, cycles, components
- Standard graph bestiary: trees, complete graphs, partite graphs
- Variations: multigraphs, pseudographs, directed graphs
- Degrees, degree formula, graphical sequences
- Digression: planar graphs, Euler’s equation, classification of Platonic solids (regular planar graphs)
- Spanning trees, connectivity, Menger’s Theorem
- Eulerian tours, Hamiltonian cycles
- Flows in directed graphs, max-flow/min-cut theorem
- Vertex colorings, chromatic polynomials
- Edge colorings, Vizing’s theorem
- Extremal topics: Ramsey, Turán

Grading

- 10%: Worksheets (graded for completion)
- 25%: Homework (weekly, due Thursdays)
- 25% each: Midterm exams (Feb 27, April 16 take-home exam, handed in online)
- 15%: Final exam (take-home exam, handed in online)