### Math 1230: Graph Theory

#### Professor Richard Kenyon Tel. 863-6406 rkenyon -at- math dot brown dot edu office: Kassar 305 Office hours: Mondays 12:30-1:30pm

Text: Introduction to Graph Theory, 2nd edition by Douglas West

Course outline: We will cover most of the material in chapters 1-7, and possibly some material of chapter 8.

There will be homeworks collected weekly and one midterm.
The final grade will be weighted as follows: Homework 35%, midterm 20%, final 45%.

## Final Project:

Instead of a final exam we will have a final project. I expect around 10 typed pages on a subject of your choice related to graph theory. The write-up should contain some result and its proof. You will also give a 15 minute presentation of your project in class. The due date for the written part of the project is May 8, 5pm.

Possible project ideas:

Graph genus
Tutte polynomial
4-coloring problem
NP-completeness
Random planar maps
Erdos-Renyi random graphs
Graphons
Szemeredi regularity Lemma
Expander graphs

### Homework:

Late homework will not be accepted. The lowest homework grade will be dropped.
It is expected that your homework should involve up to 10 hours of work per week. If you are spending considerably more time than this, let me know.

Homework 1 due Tuesday Jan 31 in class
1.1.11, 1.1.14, 1.1.21, 1.1.22, 1.1.27

Homework 2 due Tuesday Feb. 7 in class
1.1.26, 1.1.29, 1.1.36, 1.1.42, 1.1.43

Homework 3 due Tuesday Feb. 14 in class
1.2.17, 1.2.18, 1.2.29, 1.2.39, 1.3.2, 1.3.9, 1.3.14

Homework 4 due Thursday Feb. 23 in class
1.3.59, 1.4.14, 1.4.15, 1.4.38, 2.1.20, 2.1.23

Homework 5 due Tuesday Mar 7 in class
2.2.6, 2.2.10, 2.2.12, 2.3.3, 2.3.10, 2.3.16, 2.3.23

Homework 6 due Tuesday Apr 4 in class
3.1.18, 3.1.24, 3.3.6, 4.1.8, 4.1.31, 4.2.8, 4.2.35

Homework 7 due Tuesday Apr 11 in class
4.3.3, 4.3.14, 5.1.7, 5.1.22, 5.1.28, 5.1.33

Homework 8 due Tuesday Apr 18 in class
5.2.6 (Hint: see page 210 of this ), 5.2.22, 5.3.7, 5.3.16, 6.1.17, 6.1.20