Graph Theory - 0366.3267
Procedural Matters:
Prerequisite Courses:
Discrete Mathematics or Introduction to Combinatorics and Graph
Theory, Linear Algebra, Introduction to Probability.
Exercises will be given during the course and will account for 10% of the
final grade.
There will also be a final exam.
Text books:
Most of the topics covered in the course appear in the
books listed below (especially the first three).
Graph Theory,
by J. A. Bondy and U. S. R. Murty,
Springer, 2008.
Introduction to Graph Theory,
by D. B. West,
Prentice Hall, 1996.
Graph Theory,
by R. Diestel,
Springer, 1997.
The Probabilistic Method, third edition,
by N. Alon and J. H. Spencer, Wiley, 2008.
Brief syllabus:
Graphs and subgraphs, trees, connectivity, Euler tours,
Hamilton cycles, matchings, Hall's Theorem and Tutte's Theorem,
edge coloring and Vizing's Theorem,
independent sets, Turan's Theorem and Ramsey's Theorem,
vertex coloring, planar graphs, directed graphs,
probabilistic methods and linear algebra tools in Graph Theory.
More relevant information, including a more detailed syllabus and
some exams from previous years, appear in:
Graph Theory
Course Outline (preliminary: to be updated during the term):
-
Nov 2:
Graphs and subgraphs, bipartite graphs, connected components,
degrees and applications
-
Nov 9:
Sperner's Lemma and Brouwer's fixed point theorem, trees, Cayley's
formula
-
Nov 16:
The matrix tree theorem
-
Nov 23:
Connectivity, Mader's Theorem, Menger's Theorem
-
Nov 30:
More on Menger's Theorem, Eulerian cycles, Hamilton cycles
-
Dec 7:
Dirac's Theorem, Chvatal-Erdos' Theorem, matchings, Hall's Theorem
-
Dec 14:
Theorems of Konig, Tutte, Petersen
-
Dec 21:
Edge coloring, Vizing's Theorem
-
Dec 28:
Cliques and Independent sets, Ramsey's Theorem, Schur's Theorem
-
Jan. 4:
Turan's Theorem,
Vertex coloring, Brooks' Theorem
-
Jan. 11:
More on Brooks' Theorem,
Graphs with high girth and high chromatic number
-
Jan. 18:
Planar graphs, Euler's formula, duals, comments on
Kuratowski's Theorem, and on the Four Colors Theorem
-
Jan. 25:
Tools from Linear Algebra
-
Feb. 1:
Solution of exercises, Concluding remarks
Exercises
List of Theorems
The site of
Shlomi Rubinstein contains several previous exams and solutions
to some of the questions in them.