Graph Theory — GRT

  • Instructor: Casey Tompkins and Nika Salia
  • Contact: ctompkins496 at at
  • Prerequisites: Some degree of mathematical maturity is needed for this relatively fast paced course. No prior knowledge of graph theory is required.
  • Text:R. Diestel, Graph Theory (available as a digital edition, too) + handouts

Course description: A brief overview of the basic concepts of graph theory will be followed by an in-depth discussion of some classical chapters of graph theory as well as some aspects of a current area: information theoretic graph theory.

Topics covered:




Graphs, paths and cycles, independent sets, cliques, trees, spanning trees, cycle structure of graphs, Euler tours.

Hamilton cycles

Sufficient conditions for Hamiltonicity, theorems of Dirac, Ore, Pósa, Chvátal.
Hamilton cycles containing given edges.


Hall's theorem, König theorem, Tutte's theorem, stable matchings, Gale-Shapley theorem.


Chromatic number, its relation to the clique number, Zykov’s and Mycielski’s constructions, coloring edges, Vizing’s theorem, list coloring, chromatic number of the plane.


Planar and plane graphs, Kuratowski’s theorem, Euler’s formula, 5-color theorem, Thomassen’s theorem on list coloring of planar graphs, graph minors.

Extremal graph theory

Turán's theorem, Erdős-Stone-Simonovits theorem, Erdős-Gallai theorem, Erdős-Sós conjecture, extremal graphs not containing cycles of a given length, saturation, Erdős-Hajnal-Moon theorem.

Network flows and connectivity

Networks, Ford-Fulkerson theorem, vertex and edge connectivity, Menger's theorems, Mader’s theorem.