
Reexam
The date for the oral reexam is 18.6.2011.
Here is a list of the original
exam topics.
Course Log / Time Table
Numeric citations refer to the 4th edition of Diestel's book (see below).
Week  Events  Content 
5 (31.1.)* 
Tue 1416 U35 & Wed 1618 ISR 
The Basics.
We have treated Sections 1.1, 1.2, 1.3, 1.6, and 1.8.
Please work out the proofs of Propositions 1.3.2, 1.4.1, and 1.4.2:
The proofs are easy and instructive.
Homework is to prepare Exercises 6 and 16 (4th edition!) from Chapter 1
for Wed 2.2.2011 and to read Chapter 1.5 until week 6.
You might either present the solutions to the exercises on Wednesday,
or hand in your written solutions for correction.

6 (7.2.) 
Tue 1416 U35 & Wed 1618 ISR  Matchings, Covering, Packing.
We have treated Sections 2.1 (without Theorem 2.1.4) and 2.2 (without Theorem 2.2.3).
Homework is to prepare Exercises 1 and 18.
We touched the problem of finding a factor H in a graph such that the degree function of H
equals some given function f: This can be reduced to finding a 1factor in some auxilary graph.

7 (14.2.) 
Tue 1418 U35  Connectivity.
We have treated Proposition 3.1.1, Lemma 3.2.4, and Theorem 3.2.5.
Theorem 3.2.4. has been generalized as follows:
Suppose that G is a kconnected graph on more than k+1 vertices and x is a vertex
such that G/e is not kconnected for every edge e incident with x.
Then there exists a separating vertex set S of size k containing x and a neighbor
of x such that GS has a component with less than k/2 vertices. 
Convince yourself again that Lemma 3.2.4 follows from this.
As homework, prove that it implies that every vertex of a 2connected graph G
on more than 3 vertices is incident with an edge e such that G/e is 2connected.
We considered the second proof of Menger's Theorem 3.3.1, by path extension,
and its corollaries 3.3.4 and 3.3.5.
More homework: Work out the proof of the global versions, Theorem 3.3.6.

8 (21.2.) 
Tue 1418 U35  Planar Graphs.
Starting with the definitions of plane and planar graphs, we looked at combinatorial properties
of the facial cycles, on which the proof of Kuratowski's Theorem relies. Essentially, these
are: In a 2connected plane graph, the boundary of every region is a cycle (not necessarily induced),
whereas in a 3connected plane graph, the boundary of every region is an induced cycle,
and in a plane 2connected graph, every edge is on the boundary of exactly 2 regions.
The rigid proofs of these facts are tedious, and for brevity I have skipped them
(they are, however, in the book). Moreover, we have looked at two methods how to
reembed a plane graph such that an arbitrary region turns into the unbounded region
of the reembedding.
We have proved  by double counting, not using Euler's formular  that the two Kuratowski graphs
are not planar. We defined minors and subdivisions (see Section 1.7),
made a brief excursion to graph minor theory and graphs on higher surfaces,
and gave a compact proof of Kuratowski's Theorem (see Section 4.4).
This was all quite different from the book proofs,
mainly because time was short, but the essential arguments can be found in
Sections 4.1, 4.2, and 4.4 as well.
Homework: Work out the proofs of Theorem 4.2.9 and Corollary 4.2.10.
Use the latter to proof that every planar graph has a 6coloring,
i. e. a function assigning a color out of {1,2,3,4,5,6} to each vertex such that
adjacent vertices receive distinct colors.
Try to find a procedural description for the fact that H is a topological minor of G, similar
to the one in Corollary 1.7.3 (Hint: You might declare some contractions as illegal).

9 (28.2.) 
Tue 1418 U35  Vertex Colouring.
We treated Theorem 5.1.1 and Proposition 5.1.2, as well as the bounds to the chromatic number
obtained from counting edges between color classes (Proposition 5.2.1)
and greedy coloring (Proposition 5.2.2).
The qualitative statement of Corollary 5.2.3 is that high chromatic number forces a subgraph of
high minimum degree. Try to find similar statements in the course where different invariants
are involved (such as connectivity and average degree).
We treated Brooks' Theorem (Theorem 5.2.4), where the Kempe chains from Proposition 5.1.2 came back.
(Recall that an a,bKempechain in a vertexcolored graph is a component of the subgraph induced
by colors a and b. Exchanging the two colors everywhere in such a chain
produces a new (properly) colored graph.)

10 (7.3.) 
Tue 1418 U35  Hadwiger's Conjecture / Edge Colouring / Extremal Graph Theory.
As an addendum to vertex colorings, we have introduced Hadwiger's Conjecture (see introduction section 7.3),
one of the most important open questions in Discrete Mathematics.
We then treated Vizing's Theorem (Theorem 5.3.2). Note that, again, we used colour exchange
 now along the edges of paths  as to modify given edge colorings; this method provides
a very simple proof of König's Theorem that the chromatic index of a bipartite
graph equals its maximum degree (Proposition 5.3.1). 
We then touched part of the material in Chapter 7 on extremal graph theory (Theorem 7.1.1).

11 (14.3.) 
Tue 1418 U35  Hamilton Cycles.
The two most important open questions in this part of the theory are
Chvatal's ttoughConjecture that there exists a t such that every ttough graph
is hamiltonian, and Thomassen's Conjecture that every 4connected line graph is hamiltonian.
We treated a number of necessary or sufficient conditions for a graph to be hamiltonian
(Section 10.1 except for Theorem 10.1.3) and then turned to Chvatal's theorem on Hamiltonian sequences
(Theorem 10.2.1).
Observe that Dirac's Theorem (10.1.1) is an immediate consequence of 10.2.1.
To find a proof for Corollary 10.2.2 is a good excercise.
There are conditions similar to those from Theorem 10.2.1 ensuring degree sequences to
be kconnected or (much more difficult) kedgeconnected.

*: The date (dd.mm.) indicates monday of the respective week.
Contents
Graph theory is a comparatively young area of mathematics, with tight links to
both theoretical and applied computer sciences. This introductory course treats
a number of classic graph problems and the related theorems, and illustrates
that graphs and networks are omnipresent models in science and technology.
Although, at this level, graph theory could be considered as a part of
general math/cs education, the audience will encounter open research
problems soon.
For more intro, see the Wiki article Graph Theory.
Provided that some participants get crazy about graphs and their relatives,
I will offer a course Graph Theory II as a followup in the 4th quarter,
and for those who really cannot get enough of it I have two reading courses
on Graph Connectivity Theory and on Matroids in my mind and in my files
(as preparation for a master thesis in the beginning
of the next academic year).
Literature
The material is covered by the comprehensive textbook
Graph Theory by
R. Diestel, 4th edition, SpringerVerlag Heidelberg (2010).
For a free preview version (the entire book for free online viewing,
in slow lowquality PDF), as well as for pay versions,
see diestelgraphtheory.com.
There are paper copies of elder editions (they will suffice), as well
as a bunch of further textbooks in the MM810 slot in IMADA's library.
Prerequisites
Basic notions from linear algebra should be known,
and basic notions and methods from abstract algebra
should have been encountered.
