Graph Theory, Rutgers Math 428, Spring 2020

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)