Graph Theory
Graph theory studies vertices and edges through connectivity, coloring, minors, flows, and extremal structure.
Planar graphs and minors is the largest field, with over two fifths of the subject's articles, most of them on curves and regions in the square lattice \(\mathbb{Z}^2\). The discrete Jordan curve theorem gives a connected lattice subgraph with as many edges as vertices exactly one bounded region, Hopf's Umlaufsatz says that a simple closed lattice walk with at least three steps and no U-turns turns through \(\pm 4\) quarter turns, and a discrete Gauss–Bonnet formula relates the corners of a polyomino to its Euler characteristic. Beyond the lattice, the field has the Robertson–Seymour theorem: every minor-closed family of finite graphs is defined by finitely many forbidden minors.
Graph coloring has the theorems of Brooks and Vizing, the four color theorem, the Kneser–Lovász theorem that the Kneser graph \(K(n, k)\) has chromatic number \(n - 2k + 2\), and the weak perfect graph theorem. Algebraic graph theory has Kirchhoff's matrix-tree theorem, and the pentagon has Shannon capacity \(\sqrt{5}\). Matchings and flows has the existence of stable matchings in the stable marriage problem, Kőnig's theorem and the max-flow min-cut theorem, and paths, cycles and connectivity has Menger's theorem, the theorems of Dirac and Ore on Hamiltonian cycles, and Fleischner's theorem that the square of a 2-connected graph is Hamiltonian.
- Paths, cycles and connectivity
- Graph coloring
- Matchings and flows
- Independence, cliques and domination
- Extremal graph theory
- Ramsey theory for graphs
- Algebraic graph theory
- Planar graphs and minors
- Graph invariants and labelings
- Directed graphs and tournaments
- Graph families and operations
- Random graphs and graph limits
Loading dependency explorer…
The dependency explorer needs JavaScript and its graph data.