Graph Theory (Fall 2015)
Among topics that will be covered in the class are the following: 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, Turán's theorem and Ramsey's theorem, vertex coloring, planar graphs, directed graphs, probabilistic methods and linear algebra tools in graph theory.
Prerequisite courses: Discrete mathematics or Introduction to combinatorics and graph theory, Linear algebra, and Introduction to probability.
Homework exercises will be given during the course and will account for 10% of the final grade. There will also be a final exam.
The course will be taught in English.
B. Bollobás, Modern Graph Theory, Springer, 2002
J. A. Bondy and U. S. R. Murty, Graph Theory, Springer, 2008
R. Diestel, Graph Theory, Springer, 2012 (4th edition)
D. B. West, Introduction to Graph Theory, Pearson Prentice Hall, 2001 (2nd edition)
M. Aigner and G. Ziegler, Proofs from THE BOOK, Springer, 2014 (5th edition)
N. Alon and J. H. Spencer, The Probabilistic Method, Wiley, 2008 (3rd edition)
L. Lovász, Combinatorial problems and exercises, AMS Chelsea Publishing, 2007 (2nd edition)
Basic definitions; graph isomorphism, labeled and unlabeled graphs; the adjacency and the incidence matrices; subgraphs and induced subgraphs; the complement and the line graph of a graph; complete and empty graphs, cliques and independent sets; bipartite graphs; vertex degrees; degree sum formula and the handshaking lemma; walks, trails, paths and cycles, girth and circumference; every u,v-walk contains a u,v-path; the longest path and cycle in a graph of a given minimum degree; connectivity and connected components; Sperner's lemma (in dimension 2); Brouwer's fixed point theorem (in dimension 2)
Derivation of Brouwer's fixed point theorem (in dimension 2) from Sperner's lemma; trees and forests; basic properties of trees: every nontrivial tree contains at least two leaves, deleting a leaf from a tree yields a smaller tree; four equivalent definitions of a tree; edge contraction and the contraction–deletion recursive formula for the number of spanning trees; Cayley's formula for the number of labeled trees with n vertices (with proof); Kirchhoff's maxtrix tree theorem: the statement and derivation of Cayley's formula
Two proofs of Kirchhoff's matrix tree theorem; the Cauchy–Binet formula; the Lindström–Gessel–Viennot lemma; connectivity of a graph
Highly connected subgraphs in graphs of large average degree (Mader's theorem); edge-connectivity; κ(G) ≤ κ'(G) ≤ δ(G); structural characterization of 2-connected graphs ("ear decomposition"); blocks and block-decompositions; Menger's theorem
Proof of Menger's theorem; global version of Menger's theorem; the Fan Lemma; Eulerian circuits; the characterization of Eulerian multigraphs; Hamilton cycles; Dirac's theorem; Ore's theorem
The Chvátal–Erdős theorem; matchings, factors, and vertex covers; Hall's marriage theorem and corollaries: every nonempty regular bipartite graph has a perfect matching, every regular graph with positive even degree has a 2-factor; systems of distinct representatives; König's theorem; Tutte's matching theorem
Every bridgeless 3-regular graph has a perfect matching; vertex coloring; relations between the clique number, the chromatic number, and the independence number; the Nordhaus–Gaddum theorem; the greedy coloring algorithm; degeneracy of a graph; Brooks' theorem
Color-critical graphs; color-critical graphs have no cutvertices; every (k+1)-critical graph is k-edge-connected (Dirac's theorem); a construction of triangle-free graphs with large chromatic number; graphs with large chromatic number and no short cycles; edge coloring; χ'(G) = Δ(G) for bipartite G (König's theorem)
(due on November 15)
(due on December 6)
(due on December 20)