Instructor: Robin Thomas
Textbook: Diestel, Graph Theory.
Other texts you may wish to consult:
Bollobas, Modern Graph Theory (recommended source)
West, Introduction to Graph Theory
Bondy and Murty, Graph Theory with Applications
Even, Graph Algorithms
Lovasz, Combinatorial Problems and Exercises
Notes on planar graphs
Lecture Schedule: Fundamentals, Matching, Connectivity, Planar graphs, Coloring, Extremal Problems, Ramsey Theory, Random Graphs.Lecture notes from last year: Lecture 1 Lecture 2 Lecture 3 Lecture 4 Lecture 5 Lecture 6 Lecture 7 Lecture 8 Lecture 9 Lecture 10 Lecture 11 Lecture 12 Lecture 13 Lecture 14 Lecture 15 Lecture 16 Lecture 17 Lecture 18 Lecture 19 Lecture 20 Lecture 21 More on lecture 21 Lecture 22 Lecture 23 Lecture 24 Lecture 25 Lecture 26 Lecture 27 Lecture 28 Lecture 29 Lecture 30
Grades: Approximately 30% homework, 30% midterm, 40% final.
Midterm exam. 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. The midterm has been scheduled for Oct 8. It will cover topics up to and including coloring and the first seven problem sets.
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 problems
Week 6 problems
Week 7 problems
Week 8 problems
Week 9 problems
Week 10 problems
There are no week 11 problems. Instead, here is an extra credit problem. Let G be a 2-connected graph drawn on the sphere. On the boundary of each face there is a car that at time t=0 starts at some point of the boundary and drives in clockwise direction along the boundary and at time t=1 it ends up at the original starting place after having gone around the boundary of the face exactly once. Each car travels at its own speed, which may vary with time and may be zero at times, but no car travels backward. Prove that some two cars will collide (end up in the same point at the same time).
Week 12 problems
Week 13 problems
Week 14 problems
Week 15 problems
This completes the weekly sets. There will be no Week 16 set.
Thursday December 12, 11:30AM-2:20PM in Skiles 246
(the same room where the class meets).
You will be permitted to bring one letter size sheet of notes,
and you will be required to turn it in at the conclusion of the
You may be asked to state theorems we covered in class.
Homework: Each homework problem must be turned in on
size paper. The text must be typed in 10pt font or larger. Figures and
formulae may be drawn by hand in black ink. Do not fold pages or bend
Your work must be scannable at 300dpi. Electronic submission is allowed
in pdf format. Due dates will be strictly enforced. Clarity of
ease of expression, mathematical elegance and overall physical
will all be factors in grading. A signed cover page
must accompany each submission.
Homework 1. Solution is available on t-square.
Homework 2. Solution is available on t-square.
Homework 3. Solution is available on t-square.
Homework 4. Solution is available on t-square.
Homework 5. Solution is available on t-square.
Honor Code: Discussing class material including problem sets is encouraged. However, no collaboration is allowed on problems assigned for homework, midterm or final.
Office hours: Tuesday and Thursday 2:00-2:30 and after class, 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