# Graph Theory

## 640:428, Fall 2019

## Course Info

Instructor: Swastik Kopparty (swastik.kopparty@gmail.com)

Class Time and Place: Tuesdays and Thursdays 1:40 pm - 3:00 pm, in Hill 009

Office Hours: Thursdays 3pm-4pm in Hill 432

Prerequisites: CALC3 and 640:250 (linear algebra)

References: Chartrand & Zhang (A first course in graph theory)

## Syllabus

This course will be an introduction to graph theory.
Topics will include:
- Trees
- Connectivity
- Eulerian tours
- Matchings, flows and cuts
- Coloring
- Extremal graph theory
- Ramsey Theory
- Random walks
- Applications to other areas of mathematics and theoretical computer science

There will be weekly problem sets.

Grading: Homework (30%), Midterm (30%), Final (35%), Participation (5%)

## Homework

**HW 0, Due Wednesday September 4:** Send an email to swastik.kopparty@gmail.com with subject "MATH428 HW 0" with:
(a) name, (b) major, (c) year, (d) related courses you have taken (e) anything in particular you're hoping to learn about in this course.

** HW 1**, Due Thursday September 12, solutions

** HW 2**, Due Tuesday, October 1, solutions

** HW 3**, Due Tuesday, October 15

** HW 4**, Due Thursday, November 7

** HW 5**, Due Tuesday, December 10, solutions

## Lecture Schedule

- September 3: introduction, basic terminology
- September 5: isopmorphism, connectedness, acyclicity
- September 10: trees
- September 12: bipartite graphs
- September 17: Eulerian tours
- September 19: Hamiltonian cycles
- September 24: degree sequences
- September 26: planar graphs
- October 1: coloring planar graphs
- October 3: vertex coloring and edge coloring
- October 8: Ramsey's theorem
- October 10: Erdos's theorem on Ramsey numbers
- October 15: miscellaneous
**October 17: MIDTERM - IN CLASS **
- October 22: midterm analysis, introduction to matchings
- October 24: matchings, Hall's marriage theorem
- October 29: MAGIC TRICK, augmenting paths, algorithms to find matchings
- October 31: analysis of the augmenting paths algorithm
- November 5: finding perfect matchings using the determinant of a matrix
- November 7: stable marriages
- November 12: flows, cuts
- November 14: proof of the max-flow min-cut theorem
- November 19: Menger's theorem
- November 21: k-connectivity
- November 26: THERE IS CLASS (despite day change) adjacency matrices, random walks
- November 28: NO CLASS (Thanksgiving)
- December 3: eigenvalues of the adjacency matrix, more random walks
- December 5: de Bruijn graphs, review
- December 10: review
**December 16: FINAL EXAM - 8AM-11AM, in the usual classroom (Hill 009) **