A Bit of History
This part gathers three separate but deeply connected threads:
- Claude Berge (whose augmenting-path matching theorem appeared in Part 16) conjectured in 1961 what became known as the Strong Perfect Graph Conjecture — a deep structural statement about "perfect" graphs. It stood open for 45 years until Maria Chudnovsky, Neil Robertson, Paul Seymour, and Robin Thomas finally proved it in 2006, in a paper spanning well over 150 pages.
- The graph isomorphism problem — deciding whether two graphs are structurally identical — sat for decades in a strange complexity limbo: known to be in NP, but neither known to be solvable in polynomial time nor proven NP-complete. In 2015, László Babai announced a quasipolynomial-time algorithm, a landmark result that made global headlines in the theoretical computer science community (and was itself briefly retracted and then re-confirmed after a gap was found and fixed in 2017 — a vivid reminder that even celebrated proofs get scrutinized and strengthened).
- Neil Robertson and Paul Seymour spent from 1983 to 2004 publishing a sequence of over 20 papers, collectively titled "Graph Minors," culminating in a proof of what was previously Wagner's conjecture: every graph property closed under taking minors can be characterized by a finite list of forbidden minors. It is widely regarded as one of the deepest and most difficult results in all of combinatorics, and it earned both mathematicians the prestigious Fulkerson Prize.
Special Graph Families
Beyond the families introduced in Part 4 (trees, bipartite, complete graphs), several structured families recur throughout advanced graph theory:
- Chordal graphs: every cycle of length 4 or more has a "chord" — an edge connecting two non-adjacent vertices in the cycle. Chordal graphs admit a perfect elimination ordering, which makes many otherwise NP-hard problems (like graph coloring and maximum clique) solvable in polynomial time on them.
- Interval graphs: vertices represent intervals on a real line, with edges between overlapping intervals. A special case of chordal graphs, and the natural model for scheduling and resource-allocation problems.
- Cographs (complement-reducible graphs): built recursively from single vertices via disjoint union and complementation — arise naturally in the study of modular decomposition.
Perfect Graphs
A graph is perfect if, for every induced subgraph, the chromatic number equals the size of the largest clique. Bipartite graphs and chordal graphs are both perfect; odd cycles of length \(\geq 5\) (and their complements) are the simplest imperfect examples.
Berge's Strong Perfect Graph Theorem (conjectured 1961, proved 2006) gives a beautifully clean characterization: a graph is perfect if and only if it contains no odd "hole" (an induced odd cycle of length \(\geq 5\)) and no odd "antihole" (the complement of one) as an induced subgraph. This single forbidden-subgraph statement resolves a problem that had resisted proof for nearly half a century.
The Graph Isomorphism Problem
Two graphs \(G_1\) and \(G_2\) are isomorphic if there is a bijection between their vertex sets that preserves all adjacency relationships — informally, they are "the same graph" drawn or labeled differently. Determining this in general is famously one of the few natural problems in NP whose complexity status remains genuinely unresolved: it is not known to be in P, and (unlike the vast majority of "hard-looking" combinatorial problems) it is not believed to be NP-complete either, based on structural evidence from complexity theory.
Babai's 2015 quasipolynomial algorithm — running in time \(2^{O((\log n)^c)}\) for some constant \(c\) — was the first major improvement in decades over the previous best (subexponential but not quasipolynomial) bound, and it remains an active area of research to determine whether a true polynomial-time algorithm exists.
Graph Minors
Recall from Part 17 that a minor of a graph \(G\) is obtained by any sequence of the following operations:
- Deleting a vertex (and its incident edges)
- Deleting an edge
- Contracting an edge (merging its two endpoints into one vertex)
A graph family is minor-closed if, whenever a graph \(G\) belongs to the family, every minor of \(G\) also belongs to the family. Planar graphs are minor-closed (any minor of a planar graph is still planar) — which is exactly why Wagner's theorem could phrase planarity as "avoiding \(K_5\) and \(K_{3,3}\) as minors."
The Robertson-Seymour Theorem
The crown jewel of this area, the Robertson-Seymour graph minor theorem, states two remarkable facts simultaneously:
Formal Statement
Well-quasi-ordering: in any infinite sequence of graphs, some earlier graph in the sequence is a minor of some later graph — there is no infinite "antichain" of graphs under the minor relation.
Consequence: every minor-closed graph family can be characterized by a finite set of forbidden minors — exactly as planarity is characterized by forbidding \(\{K_5, K_{3,3}\}\).
The theorem is famously non-constructive in a striking way: it guarantees a finite forbidden-minor list exists for any minor-closed property, but does not tell you what that list is, or even how large it might be, for a given property. Discovering the actual forbidden-minor lists for specific properties (beyond planarity's well-known pair) remains an active research area in its own right.
Treewidth & Tree Decompositions
A central tool the Robertson-Seymour proof relies on — and one with enormous independent algorithmic value — is treewidth, a measure of how "tree-like" a graph's structure is. A tree decomposition arranges the graph's vertices into a tree of overlapping "bags," and the treewidth is (roughly) the size of the largest bag minus one, minimized over all valid decompositions. Trees themselves have treewidth 1; cycles have treewidth 2; complete graphs \(K_n\) have treewidth \(n-1\) (the worst case).
Treewidth matters enormously in practice because many NP-hard problems (independent set, graph coloring, Hamiltonian cycle) become solvable in time exponential in the treewidth but only linear in the number of vertices — the basis of an entire subfield called fixed-parameter tractable (FPT) algorithms, which trades "hard in general" for "fast when the underlying structure is nearly tree-like."
Real-World Applications
Database Query Optimization via Treewidth
Modern database query engines model complex join queries as graphs, where tables are vertices and join conditions are edges. Queries whose join graphs have low treewidth can be evaluated with algorithms whose runtime is provably close to optimal, while queries with high treewidth resist efficient evaluation regardless of clever indexing — a direct, practical payoff from what began as a purely structural graph-theoretic concept in the Robertson-Seymour program.
Exercises
- Verify that any tree is a chordal graph, and explain why (hint: trees have no cycles of length 4 or more to begin with, so the chordal condition holds vacuously).
- Explain the difference between a graph subdivision (used in Kuratowski's theorem) and a graph minor (used in Wagner's theorem), giving a small example where a graph is a minor of another but not a subdivision.
- Compute the treewidth of a simple cycle graph \(C_5\) by constructing an explicit tree decomposition and identifying its largest bag.
- Challenge: Research one specific minor-closed graph family beyond planar graphs (e.g., graphs embeddable on the torus, or graphs of bounded treewidth) and identify (or look up) its forbidden-minor characterization.
Conclusion & Next Steps
From perfect graphs to isomorphism to the sweeping Robertson-Seymour theorem, this part has shown just how much structure hides beneath "does this graph look like that one." The next part turns from structural characterization to counting: how many edges can a graph have before it is forced to contain a particular substructure — the domain of extremal and Ramsey theory.
Next in the Series
In Part 19: Extremal Graph Theory & Ramsey Theory, we'll meet Ramsey's theorem, Turán's theorem, and the surprising guarantee that complete disorder is impossible once a structure grows large enough.