Let's be clear. I'm not here to hold your hand through complex mathematical concepts. But if you insist on delving into this, I'll lay it out. Just don't expect me to be thrilled about it.
Theorem Relating Graph Minors and Topological Embeddings
This theorem, a cornerstone in the intricate field of graph theory, establishes a profound and fundamental link between the abstract concept of graph minors and the geometric notion of topological embeddings. It's a monumental achievement, presented as the seventeenth in a series of twenty-three papers authored by the formidable duo Neil Robertson and Paul Seymour. The proof itself is a labyrinth, a testament to its sheer length and complexity. For those who find the original text a bit… dense, surveys by Kawarabayashi & Mohar (2007) and Lovász (2006) offer more accessible, though still demanding, insights into the theorem and its far-reaching consequences.
Setup and Motivation for the Theorem
Imagine a graph, G. A minor of G, let's call it H, is essentially a graph derived from a subgraph of G through a series of edge contractions. If G doesn't contain H as a minor, we say G is H-free. The theorem posits that if G is a vast, H-free graph, there must be a compelling structural reason for this absence. It’s not arbitrary. The theorem provides this reason by suggesting that such graphs either lack the necessary "thickness" to contain H, or they can be, more or less, topologically embedded onto a surface too simple to accommodate H.
Think of it this way: if H is a simple, planar graph, then G being H-free likely means it’s "too thin." If H is more complex, non-planar, then both reasons – being too thin and being embeddable on a simpler surface – come into play. We need to unpack these ideas.
Tree Width
The tree width of a graph G quantifies its "thinness." A connected graph with tree width one is, by definition, a tree. If its tree width is two, it's a series–parallel graph. The intuition is that a graph with a large tree width resembles a massive tree where the nodes and edges have been substituted with smaller, intricate graphs.
A crucial property is that if H is a minor of G, then the tree width of H cannot exceed that of G. This leads to a vital corollary: for any given planar graph H, there exists a constant k such that any H-free graph must have a tree width less than k. However, this k can be disproportionately large compared to the tree width of H itself. This is why the theorem is described as revealing the rough structure of H-free graphs; it’s not always a precise blueprint. An exception is when H is the complete graph on four vertices, K₄, where k is a mere 3.
Surface Embeddings
A surface, in the simplest terms, is a space that locally resembles a disc. These surfaces fall into two broad categories: orientable (like the sphere, torus, or double torus) and nonorientable (such as the real projective plane or the Klein bottle). A graph embeds on a surface if it can be drawn on that surface without its edges crossing, except at their shared vertices. A graph is planar if it embeds on the sphere.
If a graph G can be embedded on a particular surface, then all of its minors can also be embedded on that same surface. This provides another "good reason" for G to be H-free: G might embed on a surface where H simply cannot.
This concept extends the famous Kuratowski theorem, which, in a form proved by Wagner (1937), states that a graph G is planar if and only if it does not contain K₅ or K₃,₃ as minors. This tells us that if G is K₅-free and K₃,₃-free, it embeds on the sphere, a surface neither K₅ nor K₃,₃ can inhabit. But for the broader graph structure theorem, this isn't quite enough. We need more sophisticated tools: clique-sums and vortices.
Clique-Sums
A clique within a graph G is a set of vertices where every pair is connected by an edge. For a non-negative integer k, a k-clique-sum of two graphs, G and K, is formed by selecting cliques of size m (where m ≤ k) from each graph, merging these cliques into a single one of size m, and then optionally removing some edges connecting vertices within this new clique.
By repeatedly applying k-clique-sums to a sequence of graphs G₁, G₂, ..., G<0xE2><0x82><0x99>, we can construct a new, larger graph. In fact, a graph possesses a tree width of at most k if and only if it can be constructed through k-clique-sums from a collection of graphs, each having at most k+1 vertices.
As Corollary 1 suggests, k-clique-sums of smaller graphs indeed capture the broad structure of H-free graphs when H is planar. When H is non-planar, we must also consider k-clique-sums of graphs embedded on surfaces that H cannot be embedded on. Consider H = K₅. While K₅ embeds on every surface except the sphere, there exist K₅-free graphs that are far from planar. Wagner's (1937) theorem on K₅-free graphs illustrates this:
Theorem 2. If a graph G is K₅-free, then it can be constructed via 3-clique-sums from a collection of planar graphs, along with copies of a specific non-planar graph containing 8 vertices.
It's important to note that Theorem 2 is an exact structural theorem. The graph structure theorem, however, is generally less precise. For most H, the structural description it provides includes graphs that do contain H as a minor, even though the theorem is meant to describe H-free graphs.
Vortices (Rough Description)
One might naturally wonder if an analog of Theorem 2 exists for non-planar graphs H beyond K₅. The conjecture would be: for any non-planar H, does there exist a k such that every H-free graph can be built via k-clique-sums from graphs that either have at most k vertices or embed on a surface H cannot? This is close, but not quite right. We need to allow these embedded graphs a couple of "cheats."
First, we must permit a limited number of special locations on the surface where vertices and edges can be added, and these additions are allowed to cross each other in a controlled, limited way. These locations are termed vortices, and their "complexity" is measured by a parameter called depth, which is closely tied to pathwidth.
Second, we must allow a bounded number of new vertices to be added to each of these embedded graphs that contain vortices.
Vortices (Precise Definition)
Within an embedded graph G on a surface, a face is an open region bounded by the graph's edges. If the vertices on the boundary of a face F are v₀, v₁, ..., v<0xE2><0x82><0x99>₋₁, v<0xE2><0x82><0x99> = v₀ (in circular order), then a circular interval for F is a contiguous sequence of these boundary vertices, {v<0xE2><0x82><0x90>, v<0xE2><0x82><0x90>₊₁, ..., v<0xE2><0x82><0x90>₊<0xE2><0x82><0x9B>}, where indices are taken modulo n.
Now, consider a finite list of such circular intervals, Λ, for a face F. We construct a new graph by adding a new vertex v<0xE2><0x82><0x97> for each interval L in Λ. Each v<0xE2><0x82><0x97> can connect to any subset of vertices within its corresponding interval L. Furthermore, for any two intervals, L and M, in Λ, we can add an edge between v<0xE2><0x82><0x97> and v<0xE2><0x82><0x98> if and only if L and M share at least one vertex. This resulting graph is said to be obtained from G by adding a vortex of depth at most k to face F, provided that no boundary vertex of F appears in more than k intervals in Λ.
Statement of the Graph Structure Theorem
Graph Structure Theorem. For any graph H, there exists a positive integer k such that every H-free graph can be constructed through the following process:
- Begin with a list of graphs, each embedded on a surface where H itself cannot be embedded.
- To each graph in this list, attach at most k vortices, with each vortex having a depth no greater than k.
- To each resulting graph, add at most k new vertices, known as apices, and introduce any number of edges, ensuring that at least one endpoint of each new edge is an apex.
- Finally, combine the graphs generated in step 3 using k-clique-sums.
It's worth noting that if H is planar, steps 1 and 2 might result in an empty graph. However, the bounded number of apices added in step 3 ensures the theorem remains consistent with Corollary 1.
Refinements
The graph structure theorem can be strengthened depending on the specific set of forbidden minors, H. For instance, if H contains a planar graph, then any H-minor-free graph admits a tree decomposition of bounded width. Equivalently, it can be represented as a clique-sum of graphs of constant size. [^1]
If H includes a graph that can be embedded in the plane with only a single crossing, then the H-minor-free graphs can be decomposed into a clique-sum of constant-size graphs and graphs of bounded genus, crucially, without the need for vortices. [^2]
A different kind of strengthening applies when H contains an apex graph. [^3]
See Also
Notes
- ^ Graph Minors V.
- ^ Robertson & Seymour (1993); Demaine, Hajiaghayi & Thilikos (2002)).
- ^ Demaine, Hajiaghayi & Kawarabayashi (2009).