Invitation to Graph Theory [Spring 2006]
Neil Robertson
There will be two lectures in this series. The
first will present
several problems which can be formulated with
elementary
notation and are at three levels,
recreational, course exercises
and fundamentally challenging. Some simple
basic notation
and theorems will be introduced in this
context. An example
of such a theorem states that the axiom of
choice for families
of nonempty subsets is equivalent to existence
of spanning
trees in all connected graphs. The second
lecture will complete
this material and explore some chromatic
number problems
related to contraction minors (topological
graph theory) and
vertex-deleted subgraphs
(optimization/extremal graph theory).

