Graph Theory

What you’ll study

Fundamental concepts — varieties of graphs, paths, cycles and components, degrees and distances, and cliques. Trees — their properties, spanning trees, forests, centroids, and the generation of trees and cycles. Connectivity — vertex and edge connectivity, blocks, eccentricity and Menger's theorem. Traversability — Eulerian graphs, Kuratowski's theorem, the embedding of graphs on surfaces, genus, thickness and crossing number. Graph colouring — vertex and edge colouring, the chromatic number, the five-colour theorem, the four-colour conjecture and critical graphs. Digraphs and homomorphism — different forms of connectedness, oriented graphs and tournaments, network flows and related algorithms; groups, polynomials and graph enumeration, matching and factorization, perfect graphs, the Ramsey number and Ramsey's theorem, and forbidden-graph theory.