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. The important idea is not just that these families have names: each family forbids or organizes certain patterns, and that extra structure often turns a problem that is difficult on arbitrary graphs into one that can be solved efficiently.
Three ways a graph can carry extra structure
Think of a graph family as a promise about the input. A good promise removes pathological cases and exposes an ordering, geometry, or recursive decomposition that an algorithm can exploit.
- Chordal graphs: every cycle of length 4 or more has a chord — an edge connecting two non-adjacent vertices of that cycle. This destroys the long induced cycles that make many problems difficult.
- Interval graphs: vertices represent intervals on a real line, with edges between overlapping intervals. The geometry itself gives an ordering and makes them a natural model for scheduling and resource allocation.
- Cographs (complement-reducible graphs): built recursively from single vertices using disjoint union and join/complement operations. Their recursive construction gives a decomposition tree on which many problems can be solved bottom-up.
Perfect Elimination: Why Chordal Graphs Are Friendly
A vertex is simplicial when all of its neighbors form a clique. A perfect elimination ordering (PEO) repeatedly removes a simplicial vertex until nothing remains. Chordal graphs are exactly the graphs that admit such an ordering. Algorithmically, this means we can peel the graph apart without creating a complicated boundary: when a vertex is eliminated, all of the still-relevant neighbors already know about one another.
Memory Aid: Structure Gives You an Order
Trees give parent/child order, DAGs give topological order, chordal graphs give a perfect elimination order, and interval graphs give left-to-right endpoint order. A recurring graph-algorithm pattern is: find the structural order first, then solve the problem along that order.
Perfect Graphs
Recall from Part 13 that every clique of size \(k\) forces at least \(k\) colors, so \(\omega(G) \le \chi(G)\) always. A graph is perfect when this obvious lower bound is never loose — not just for the graph itself, but for every induced subgraph.
The gap \(\chi-\omega\) is the obstruction
The 5-cycle is the smallest clean example of imperfection: its largest clique has only two vertices, but an odd cycle still requires three colors.
Bipartite graphs and chordal graphs are perfect. Odd cycles of length at least 5, called odd holes, are not; neither are their complements, called odd antiholes. Berge's Strong Perfect Graph Theorem (conjectured in 1961 and proved decades later) says these are exactly the obstructions: a graph is perfect if and only if it contains no odd hole and no odd antihole as an induced subgraph.
Why “Every Induced Subgraph” Matters
A graph might accidentally satisfy \(\chi(G)=\omega(G)\) while hiding a smaller induced subgraph where the equality fails. Perfectness is hereditary: every time you zoom in by deleting vertices, the equality must survive.
The Graph Isomorphism Problem
Two graphs \(G_1\) and \(G_2\) are isomorphic when one can be relabeled to become the other. Geometry does not matter: vertices may move, edges may bend, and labels may change. What must remain unchanged is which pairs are adjacent.
Do not compare drawings — compare adjacency
Invariants Are Filters, Not Usually Proofs
Isomorphic graphs must have the same number of vertices and edges, the same degree multiset, the same number of connected components, the same cycle counts, and many other graph invariants. A mismatch instantly proves two graphs are not isomorphic. But matching invariants usually does not prove they are isomorphic: different graphs can share many summaries. A true isomorphism needs a globally consistent vertex correspondence.
Mental Model: Fingerprints Before Full Identification
Degree sequence is like height and eye color: useful for ruling candidates out, but not enough to establish identity. Isomorphism asks for the full adjacency-preserving bijection.
Determining isomorphism in general is famously unusual in complexity theory: it is in NP, not known to be NP-complete, and no general polynomial-time algorithm is known. Babai's quasipolynomial-time breakthrough dramatically narrowed the gap, while the search for a polynomial-time algorithm remains open.
Graph Minors
Isomorphism asks whether we can change labels while preserving the graph exactly. Minor theory moves in the opposite direction: it deliberately forgets detail while trying to preserve coarse connectivity structure. A graph \(H\) is a minor of \(G\) if \(H\) can be obtained through vertex deletion, edge deletion, and edge contraction.
Delete vs. Contract: Three Ways to Simplify
| Relation | Allowed operation | What it preserves |
|---|---|---|
| Subgraph | Delete vertices/edges | Exact surviving adjacencies |
| Induced subgraph | Delete vertices only | All edges among surviving vertices |
| Minor | Delete + contract | Coarse connectivity pattern |
A graph family is minor-closed if simplifying any member by these operations never leaves the family. Planar graphs are the model example: deleting or contracting inside a planar embedding cannot force crossings. Wagner's theorem therefore recognizes planarity by the two minors that must never appear, \(K_5\) and \(K_{3,3}\).
Isomorphism vs. Minor: Exactness vs. Simplification
Isomorphism: “Are these exactly the same structure after relabeling?” Minor: “Can this simpler structure be extracted by deleting and contracting?” The first preserves everything; the second intentionally forgets detail.
The Robertson-Seymour Theorem
The crown jewel of minor theory is easiest to appreciate as a statement about obstructions. Suppose a property survives every deletion and contraction. Then failure of that property must have some minimal causes — graphs that fail the property, but whose proper minors no longer do. Robertson and Seymour proved that there can only be finitely many such minimal forbidden patterns.
Formal Statement
Well-quasi-ordering: among any infinite sequence of finite graphs, some earlier graph is a minor of some later graph; there is no infinite antichain under the minor relation.
Finite-obstruction consequence: every minor-closed family of finite graphs can be characterized by a finite set of forbidden minors.
Infinite family, finite obstruction list
Planarity is the perfect miniature example: there are infinitely many planar graphs and infinitely many non-planar graphs, but the entire boundary between them is controlled by just two forbidden minors.
The theorem is existential in a striking way: it guarantees that a finite obstruction list exists for every minor-closed family, but the theorem alone does not hand us that list for a property we care about. Finding explicit obstruction sets can itself be extremely difficult. The conceptual payoff is still enormous: a potentially infinite universe of counterexamples is controlled by finitely many minimal patterns.
Treewidth & Tree Decompositions
Treewidth measures how far a graph is from behaving like a tree. The key trick is not to force the original graph itself into a tree. Instead, we build a tree of overlapping bags, where each bag stores a small local interface of vertices. If those interfaces stay small, dynamic programming can solve a global problem by passing compact summaries from bag to bag.
The Three Rules for a Valid Tree Decomposition
Every graph vertex appears in at least one bag.
For every edge \(uv\), some bag contains both \(u\) and \(v\).
All bags containing a fixed vertex form one connected subtree.
A cycle is not a tree, but it can be processed through bags of size 3
For \(C_5\), the bags below each contain three vertices, so this decomposition has width \(3-1=2\). The repeated vertex 1 acts like a small interface that keeps the local pieces consistent.
Trees have treewidth 1, cycles have treewidth 2, and complete graphs \(K_n\) have treewidth \(n-1\). High treewidth means every decomposition needs a large interface somewhere; low treewidth means the graph can be separated into pieces that interact through only a few shared vertices.
Why This Makes Hard Problems Easier
A dynamic program does not need to remember the entire processed graph. It only remembers enough information about the current bag to connect the solved part to the unsolved part. For many classic problems, this leads to runtimes of the form \(f(k)\,n\) or \(f(k)\,n^{O(1)}\), where \(k\) is treewidth. The dependence on \(k\) may be exponential, but when \(k\) is small the algorithm can still be practical on large graphs.
Real-World Applications
Database Query Optimization via Treewidth
Complex join queries can be modeled by a graph or hypergraph whose vertices are relations/variables and whose edges encode interactions. When this structure has low treewidth, the query can often be decomposed into small overlapping pieces and evaluated by dynamic programming. High width means some intermediate interface is inherently large, which is exactly where intermediate join results can explode.
Part 18 Mental Model
Extra structure creates useful orderings/decompositions.
Clique lower bound exactly matches coloring in every induced subgraph.
Preserve the graph exactly; only labels/drawing change.
Simplify by deletion/contraction to expose hidden cores.
Minor-closed families have finitely many forbidden cores.
Small overlapping interfaces make global DP possible.
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.