Math6014 Graph Theory

This is a required class in the PhD program in Algorithms, Combinatorics and Optimization. The objective is to provide rigorous treatment of Graph Theory at the level of an introductory graduate course. You do not need to know much about Graph Theory, but you do need the mathematical sophistication of a beginning mathematics graduate student in order to succeed in the course. You will be required to write rigorous mathematical proofs of non-trivial results. In addition to mathematical correctness attention will be paid to writing in an elegant and aesthetically pleasing way. An assignment will be due approximately every two weeks. Thus, in addition to learning Graph Theory, you will get to practice and improve your proof-writing skills. See the links below for sample problems you will be required to solve.

Instructor: Robin Thomas

Textbook: Diestel, Graph Theory

Other texts you may wish to consult:
Bollobás, Modern Graph Theory (recommended source)
West, Introduction to Graph Theory
Bondy and Murty, Graph Theory with Applications
Even, Graph Algorithms
Lovász, Combinatorial Problems and Exercises

Lecture Schedule: Fundamentals, Matching, Connectivity, Planar graphs, Coloring, Extremal Problems, Ramsey Theory, Random Graphs.

Grades: Approximately 30% homework, 30% midterm, 40% final.

Midterm exam is scheduled for October 22. You will be asked to solve problems similar to proofs done in class or problems assigned in the problem sets below. You will be permitted to bring one letter size sheet of notes, one-sided only, and you will be required to turn it in at the conclusion of the examination.

Problem sets: Problem sets will be posted here. You should be able to solve these problems, because they and their variations will appear in both the midterm and the final exam. Old problems are posted below.
Week 1 problems
Week 2 problems
Week 3 problems
Week 4 problems
Week 5 problem
Week 6 problems
Week 7 problems
Week 8 problems
Week 9 problems
No week 10 problems
Week 11 problems
Week 12 problems
Week 13 problems
No week 14 problems, but here is the first part of notes on planar graphs.
Week 15 problems
Week 16 problems

Final examination. The Final examination will take place during the middle exam period on December 8 most likely in the same room where the class meets, but that will not be confirmed until later. You will be permitted to bring one letter size sheet of notes, one-sided only, and you will be required to turn it in at the conclusion of the examination. You may be asked to state theorems we covered in class.

Homework: Each homework problem must be turned in on one-sided letter size paper. The text must be typed in 10pt font or larger, figures and mathematical formulae may be drawn by hand in black ink. Do not fold pages or bend corners. Your work must be scannable at 300dpi. Electronic submission is allowed only in pdf format. Due dates will be strictly enforced. Clarity of exposition, ease of expression, mathematical elegance and overall physical appearance will all be factors in grading. A signed cover page must accompany each submission.
Homework #1 due September 3
Homework #2 due September 17
Homework #3 due October 8
Homework #4 due November 12
Homework #5 due December 3

Honor Code: Discussing problems is encouraged. No collaboration is allowed on homework, midterm or final.

Office hours: MW 2-3 and by appointment.

Office: 217B Skiles.

This document: http://www.math.gatech.edu/~thomas/TEACH/6014

Old problem sets: First set   Second set    Third set    Fourth set    Fifth set    Sixth set    Seventh set    Eighth set    Nineth set