Math 510
Introduction to Graph Theory
Spring 2022

This course is an introduction to fundamental concepts of graph theory. We study the book

To the extent there is a special emphasis, it is on the structure of graphs, in particular contributions of Tutte, arguably the greatest graph theorist of the middle of the last century. (A short biography from Tutte's University of Waterloo. The New York Times obituary. The London Times obituary.)

Another book of Tutte's that has some overlap in topics but is much shorter, less dense, and less formal, is Graph Theory As I Have Known It, Oxford University Press, 1998.

The course is not normally suitable for first-year graduate students. However, there are no specific prerequisites except the traditional "mathematical maturity". Basic graduate algebra is very helpful.

Course time and place:

PLACE: WH 309
TIME: Mon., Wed., Fri. 3:30-4:30.

Office hours:

M, W, F: 2:00-3:15 in WH 216.
I will be happy to see you at these or other times as far as possible. If necessary we can make appointments.Make sure I see you (or else I may never notice).

The Combinatorics Seminar

All students are encouraged to attend the Combinatorics Seminar, usually on Tuesdays, 1:15-2:20. There will be talks you can't understand, as well as some you can't help understanding, on all kinds of topics in graph theory and other combinatorics as well as in number theory (and sometimes both at once). (You'll be surprised how much you learn by not understanding a great many talks.)

Course Procedure

I will lecture, for the most part. I intend to explain rather than repeat what is in the book. I hope to have a lot of interaction with you, the students/audience.

Student work: You will have to work hard sometimes to understand the lectures and readings. Keep your colored pencils handy.

• Your grade will be based on a combination of handed-in problems, individual conferences, and student presentations.
• Try all the exercises at the end of the chapters. You don't have to solve all of them! I will collect your written solutions to some or all of the assignments, some from Tutte and some from the additional problems. The list of hand-in problems is not compulsory but you should turn in as many as you can.
• I will meet with each of you individually on a regular basis. Here is the schedule of individual meetings.
• There will be some student presentations later in the course, probably from the textbook.

Syllabus and Assignments

See the syllabus and schedule and the assignments page.

Health Warnings

There are absolute requirements for health precautions during the pandemic. See the accompanying health page, but note especially:

• You must have nose and mouth covered by a working face mask in class, at all times (unless drinking something—no food). If your mask falls down, you must leave class and get a new one before returning. Be prepared.
• If you feel sick, stay home. If it's Covid-19, follow isolation guidelines. And tell me about it so we can make appropriate arrangements. (If you are teaching, also tell the Chairperson Prof. Mazur; he will help you.)