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

New lecture notes in preliminary form: Lectures 28 and 29 Lecture 29 continued

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

Pfaffian orientations

Application to algebra

The discharging method

A simple planarity algorithm

Eigenvalues and expanders

The Nielsen-Schreier Theorem

Extremal Graph Theory Part 1

**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.
Date: October 8.

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

Week 1 problems

Week 2 problems. An additional problem:
Is the hypothesis |E(D)|>=2|V(D)| in the Lemma from "Application to algebra"
necessary? Could it be replaced by |E(D)|>=2|V(D)|-1 or an even
weaker assumption?

Week 3 problems

Week 4 problems

Week 5 problems

Week 6 problems

Week 7 problems

Due to the midterm exam and Fall recess there are no Week 8 problems

Week 9 problems

Week 10 problems

Week 11 problems

Week 12 problems (typo in problem 5 corrected)

Week 13 problems

Week 14 problems

Week 15 problems

Week 16 problems

**Extra credit problems** will be posted here.

Extra credit problem 1
Hint. Consider the complete bipartite graph G with vertices the rows and columns
of the board. Thus the squares of the board are in 1-1 correspondence
with edges of G. Consider the number of components of the subgraph of G
consisting of edges painted black.

Extra credit problem 2

Extra credit problem 3

Extra credit problem 4

Extra credit problem 5

Extra credit problem 6:
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).

**Final examination.**
December 10, 11:30-2:20 in Skiles 246.
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 Solutions are available on T-square.

Homework 2 Solutions are available on T-square.

Homework 3 Solutions are available on T-square.

Homework 4 Solutions are available on T-square.

Homework 5 Solutions are available on T-square.

Homework 6 Due November 20.

**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 1:45-2:15, Thursday 12:00-12:30
and by appointment.

**Office:** 217B Skiles.

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