Graph Theory -- Spring 2014
Meeting Time/Place: TUE 12:00-1:20 PM/WED 3:20-4:40 PM in Hill 525
Course Text:
Bela Bollobás, Modern Graph Theory
I do not expect to follow the book closely, and will include
some topics outside the book.
Other good graph theory texts include:
- Reinhard Diestel, Graph Theory. A preview version is available online
http://diestel-graph-theory.com/
- Doug West, Introduction to Graph Theory.
Instructor information
Basic Course Information
This is an advanced introduction to graph theory. By "advanced
introduction", I mean that I do not assume that you know any graph theory,
but I do assume mathematical sophistication.
Students are expected to be experienced in reading and writing
mathematical proofs. The formal subject prerequisites are undergraduate
math courses: advanced
calculus, linear algebra, and probability.
We will not need much from any of
these subjects.
This is a theoretical course, and most of the lectures
and homework will involve
proving theorems.
Regular attendance in the course is expected.
The grade in the course is based on problem sets. There will
be about 6 problem sets, roughly one every other week.
Announcements
<.li>(Posted 4/21/14) Two corrections two problem 5: In part b,
two occurences of the phrase "minimum degree d" were corrected
to "minimum degree at least d". Also I added a remark that
if H itself has minimum degree at least d then this is a triviality.
In part c, the number 2 has been corrected to 4.
Thanks to Nathan and Cole.
(Posted 4/19/14) In problem 6 of assignment 5, second paragraph
"Colorer" should be replaced by "Builder" in the sentence
"...Colorer will use the table to decide ...". The April
19th version of the assignment reflects this change.
Thanks to Jon Shao for finding this error.
(Posted 4/7/14) In problem 4b of assignment 4, the last
occurence of script F should be a G. I have posted a revision.
Thanks to Kristen for pointing this out.
(Posted 4/5/14)
In problem 5c of assignment 4,
the expression n^{1-2/r} has been corrected
to n^{2-1/r}. This is in the April 5 revision.
Thanks to Cole for pointing this out.
(Posted 4/1/14) I have revised/expanded problem 3 to break it
into 4 parts, two of which have
hints.
(Posted 3/31/14) In problem 4 a, I originally had
ceiling of n^2/4; it has been
corrected to floor of n^2/4. (Thanks to Kafung for the correction.)
(Posted 3/10/14) Clarification on Assignment 3,
problem 7: the parameter n is equal to |V|=|W|.
(Posted 3/5/14) I just fixed another residual error in problem
4. The final condition is now W_2 \subseteq W \subseteq W_1 union W_2.
(Previously the first W_2 was a W_1, which made the problem trivial.)
Thanks to Sijian Tang for the correction.
(Posted 3/5/14) I made some corrections to Assignment 3.
On problem 3, the word "critical" should be "maximal".
On problem 4, the sets A_1 and A_2 were corrected
to V_1 and V_2, and the sets B_1 and B_2 were corrected
to W_1 and W_2. Also I clarified the quantifiers for $V$ and $W$ in the
final line of the proof.
Thanks to Nathan Fox for pointing these out.
(Posted 2/2) Problem 7 of Assignment 1
was incorrect as stated. You are asked
to prove that two conditions on a graph are equivalent. The
second condition has been corrected to:
"$G$
has an induced subgraph that has a minimal vertex cutset
that is not a clique." (The previous incorrect version
gave the condition as "$G$ has a minimal vertex cutset that is not a clique."
(Thanks to Nathan Fox for pointing out this error.)
(Posted 1/25) Corrected a typo on Homework 1. Also in problem 3,
the phrase "every graph" was corrected to "every tree". (Thanks to
Patrick Devlin for pointing this out.)
(Posted 1/24) Homework 1 is available
Written Assignments
Please read and follow the guidelines for
homework preparation
For those of you who latex their homework and want to use the
latex file of the assignment given above, you may want to include
the latex definitions file .