**Text:** *Introduction to Graph Theory*, Doug West, ISBN 9780130144003

I expect to jump around a lot in the text, and I will certainly not
cover all of the material in it. I hope you will find the text useful
as a source of alternate expositions for the material I cover. I will
write up or copy notes for subjects which I think are not dealt
with well in the book.

**Office Hours:** 2844 East Hall, Monday 10:00-12:00 and Tuesday
2:00-3:00. I will also be at tea in the math lounge (East Hall, second
floor) from 3-5ish on Mondays. Also, please feel free
to knock on my door or e-mail me at any time.

**Professor:** David E Speyer, 2844 East Hall, speyer@umich.edu

**Course homepage:** http://www.math.lsa.umich.edu/~speyer/565

**Level:** Mixed undergraduate-graduate.

**Prerequisites:** Calculus, Linear Algebra, and comfort with mathematics.

**Student work expected:** I will give problem sets every week, due
on Tuesdays, and take-home exams when we finish a topic.

**Homework Policy:** You are welcome to consult your class notes and textbook.

You are welcome to work together with your classmates provided (1) you list all people and sources who aided you, or whom you aided and (2) you write-up the solutions independently, in your own language. If you seek help from mathematicians/math students outside the course, you should be seeking general advice, not specific solutions, and must disclose this help. I am, of course, glad to provide help!

I do not intend for you to need to consult other sources, printed or online. If you do consult such, you should be looking for better/other expositions of the material, not solutions to specific problems.

You **MAY NOT** post homework problems to internet fora seeking solutions. Although I know of cases where such fora are valuable, and I participate in some, I feel that they have a major tendency to be too explicit in their help. You may post questions asking for clarifications and alternate perspectives on concepts and results we have covered.

**Take home exams:** On take-home exams, you may not consult with other people or outside sources; you may consult your notes and textbook, and the handouts I provide.

This course will discuss many aspects of graph theory: Enumerative problems (counting substructures of graphs); optimization problems (finding the best graph in some sense) and special techniques for planar graphs (graphs you can draw in the plane).

I am a pure mathematician who tries to know something about applied math, particularly applications to computer science, so I'll try to bring out these connections as appropriate. If you let me know what fields you are working in, I will try to find applications in your subjects.

Here is a list of topics I hope to cover. We will have three midterm exams, one at the end of each section; I will select dates for them later in the term.

- Trees
- The matrix tree theorem
- Eulerian tours, de Bruijn sequences
- Counting flows, the Gessel-Viennot theorem
- Random walks on graphs
- Spectral methods in graph theory

- Matchings, Hall's marriage theorem
- Optimal matchings
- The stable matching problem
- Optimization of flows, transportation problems
- Optimization of spanning trees
- Introduction to linear and integer programming
- Introduction to NP-completeness

- Euler's theorem
- The five color map theorem
- Planar duality
- Spanning trees in planar graphs, resistor networks
- Matchings in planar graphs

Problem Set 2, due September 17th in class. Solution Set 2

Problem Set 3, due September

Problem Set 4, due October 1st in class. Solution Set 4

MIDTERM 1 distributed October 1st in class, due October 8th in class.

Problem Set 5, due October 22nd in class. Solution Set 5

Problem Set 6, due October 29th in class. Solution Set 6

Problem Set 7, due November 5th in class. Solution Set 7

Problem Set 8, due November 19th in class (no problem set due November 12th). Solution Set 8. See Propp, Lattice Structures for Orientations of Graphs, Theorem 2, for more on Problem 2.

Problem Set 9, due November 26th in class. Solution Set 9

In preparing the following lectures, I relied on a number of sources, the most helpful of which were Jon Kelner's lecture notes.