Instructor: Danny Krashen, Hill 220

Office Hours:

- Mon 2:30-3:30
- Wed 11:00-12:00

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
- Eulerian tours, Hamiltonian cycles
- 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
- 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%: In class worksheets (graded for completion)
- 25%: Homework (weekly, due Thursdays)
- 25% each: Midterm exams (tentative dates: Feb 27, April 16)
- 15%: Final exam (either in class or project, to be decided)