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 colouring and Vizing's Theorem, independent sets, Turán's theorem and Ramsey's theorem, vertex colouring, 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.
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, 2016 (5th edition) – freely available for online viewing at
diestel-graph-theory.com
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, 2016 (4th edition)
L. Lovász, Combinatorial problems and exercises, AMS Chelsea Publishing, 2007 (2nd edition)
October 18
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; long paths and cycles in a graph of a given minimum degree; every u,v-walk contains a u,v-path; connectivity and connected components
October 25
Sperner's lemma (in dimension 2); Brouwer's fixed point theorem (in dimension 2); 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; cut-edges; 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
November 1
Kirchhoff's matrix tree theorem; derivation of Cayley's formula; the Cauchy–Binet formula (without proof); connectivity of a graph
November 8
highly connected subgraphs in graphs of large average degree (Mader's theorem); edge-connectivity; κ(G) ≤ κ'(G) ≤ δ(G); structural characterisation of 2-connected graphs ("ear decomposition"); flows in directed graphs; the max-flow min-cut theorem
November 15
the integrality theorem; flows in directed graphs with vertex capacity bounds; the max-flow min-cut theorem for vertex capacity bounds; Menger's theorem; global version of Menger's theorem; the `fan lemma'; Eulerian circuits; the characterisation of Eulerian multigraphs
November 22
Hamilton cycles; Dirac's theorem; Ore's theorem; the Chvátal–Erdős theorem; matchings, factors, and vertex covers
November 29
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 (Petersen's theorem); König's theorem; Tutte's matching theorem
December 6
Every bridgeless 3-regular graph has a perfect matching; vertex colouring; relations between the clique number, the chromatic number, and the independence number; the Nordhaus–Gaddum theorem; the greedy colouring algorithm; degeneracy of a graph; Brooks's theorem
December 13
NO CLASS (Hanukkah)
December 20
Colour-critical graphs; colour-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
December 27
Edge colouring; König's theorem (χ'(G) = Δ(G) for bipartite G); Vizing's theorem (χ'(G) ≤ Δ(G)+1) without proof; Ramsey numbers; the upper bound on R(s,t) of Erdős and Szekeres; a probabilistic lower bound on the diagonal Ramsey numbers R(s,s); multicolour Ramsey numbers; Schur's theorem
January 3
Turán numbers; Mantel's theorem; Turán graphs; Turán's theorem; the Erdős–Stone theorem (without proof); Zarankiewicz's problem and the Kővari–Sós–Turán theorem; a construction of large K
2,2-free graphs based on point-line incidences
January 10
Planar graphs; the Jordan Curve Theorem (without proof); K
5 is not planar; subdivisions and minors; Kuratowski's theorem (without proof); Wagner's theorem (without proof); faces of a plane graph; the plane dual G
* of a plane graph G; duals are connected; (G
*)
* = G for connected G; Euler's formula; an upper bound on the number of edges of a simple planar graph
January 17
The four colour problem; Heawood's theorem (planar graphs are 5-colourable); the proof of Wagner's theorem (sketch)
The final exam will take place on Wednesday, the 27th of January at 9:00; the second attempt is scheduled for Tuesday, the 27th of July at 9:00.
Below is a list of theorems that were presented in class and whose proofs one is expected to know during the final exam.
List of theorems for the final exam