### 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%.

## TA sessions: Mondays 6-7pm, BH160. TA: Laura Shea

##

## 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.

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