This post continues my series on favorite theorems of the 21st century. For an overview of the categories and earlier selections, see this post.
My choice for 2001 in Combinatorics is the proof of Wagner’s conjecture, completed by Robertson and Seymour in the twentieth paper of their monumental Graph Minors series. The result is now commonly known as the Graph Minors Theorem.
Given a graph and an edge , one may construct a new graph by deleting the edge and identifying (merging) the vertices and into a single new vertex adjacent to all neighbors of and . This operation is called edge contraction. Together with deletion of edges and vertices, edge contraction forms the basic operations for producing graph minors.
A family of graphs is called minor-closed if whenever and is a minor of , then .
One of the classical examples is the family of planar graphs. Since the complete graph and the complete bipartite graph are non-planar, no planar graph can contain either as a minor. In a celebrated 1937 theorem, Wagner proved that this necessary condition is also sufficient: a finite graph is planar if and only if it contains neither nor as a minor. Thus, planarity can be characterized by a finite list of excluded minors.
In 1970, Wagner conjectured a sweeping generalization:
For every minor-closed family of finite graphs, there exists a finite set of graphs such that a graph belongs to if and only if contains none of the as a minor.
Equivalently, the conjecture asserts that in every infinite sequence there exist indices such that is isomorphic to a minor of .
Robertson and Seymour began their attack on this conjecture in 1983. Over the next two decades, they developed an extraordinarily deep and intricate structure theory for graphs, culminating in the twentieth paper of the series (submitted in 2001), which completed the proof (Robertson and Seymour 2004). The full series spans more than 500 pages and has profoundly reshaped modern graph theory.
Beyond its conceptual elegance, the theorem has powerful algorithmic implications.
For each fixed graph , there exists an algorithm to test whether an -vertex graph contains as a minor (Robertson and Seymour 1995). Combining this with the Graph Minors Theorem yields the following striking corollary:
For every fixed minor-closed family , membership in can be tested in time.
Indeed, since is characterized by a finite list of excluded minors , one can simply test whether contains any of the as a minor.
For example, for any fixed surface , there is a cubic-time algorithm to determine whether a graph can be embedded in without edge crossings.
There is, however, a subtle and somewhat paradoxical aspect to this result. For many interesting minor-closed families , the explicit list of excluded minors is unknown. Thus we know that a cubic-time algorithm exists, but in practice we may not know how to implement it because the finite obstruction set is not explicitly determined.
Few results combine structural depth, conceptual clarity, and algorithmic power in such a remarkable way. The Graph Minors Theorem stands as one of the great achievements of late 20th-century mathematics—and a fitting choice for 2001 in combinatorics.