Introduction to Graph Theory

Harvard FAS

Introduces core topics in graph theory: forests, (k-)(edge-)connectivity, (outer)planarity, (induced) subgraphs, graph minors, matchings (in not-necessarily-bipartite graphs), colorings, and (nowhere-zero) flows. Discusses the Four-Color Theorem, that every planar graph's vertices can be colored with four colors, and builds up the graph-theoretic machinery necessary for an understanding of its generalization and successor as a major open problem, Hadwiger's conjecture.