Introduction to Graph Theory
COMPSCI 1251
Subject & Catalog Number
Course Information
Description
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.
Course Notes
Students who have taken AM 107 should talk with the instructor before enrolling.
Recommended Prep
Comfort with mathematical proofs. (Diagnostic questions available on request.) Usually taught in Math 22/25/55/101 or CS 20.
Available for Harvard Cross Registration
NOTE: This course requires additional sections; you will be prompted to choose secondary components during the Add to Cart process
