# Graph structure theorem

In mathematics, the graph structure theorem is a major result in the area of graph theory. The result establishes a deep and fundamental connection between the theory of graph minors and topological embeddings. The theorem is stated in the seventeenth of a series of 23 papers by Neil Robertson and Paul Seymour. Its proof is very long and involved. Kawarabayashi & Mohar (2007) and Lovász (2006) are surveys accessible to nonspecialists, describing the theorem and its consequences.

## Setup and motivation for the theorem

A minor of a graph G is any graph H that is isomorphic to a graph that can be obtained from a subgraph of G by contracting some edges. If G does not have a graph H as a minor, then we say that G is H-free. Let H be a fixed graph. Intuitively, if G is a huge H-free graph, then there ought to be a "good reason" for this. The graph structure theorem provides such a "good reason" in the form of a rough description of the structure of G. In essence, every H-free graph G suffers from one of two structural deficiencies: either G is "too thin" to have H as a minor, or G can be (almost) topologically embedded on a surface that is too simple to embed H upon. The first reason applies if H is a planar graph, and both reasons apply if H is not planar. We first make precise these notions.

### Tree width

The tree width of a graph G is a positive integer that specifies the "thinness" of G. For example, a connected graph G has tree width one if and only if it is a tree, and G has tree width two if and only if it is a series–parallel graph. Intuitively, a huge graph G has small tree width if and only if G takes the structure of a huge tree whose nodes and edges have been replaced by small graphs. We give a precise definition of tree width in the subsection regarding clique-sums. It is a theorem that if H is a minor of G, then the tree width of H is not greater than that of G. Therefore, one "good reason" for G to be H-free is that the tree width of G is not very large. The graph structure theorem implies that this reason always applies in case H is planar.
Corollary 1. For every planar graph H, there exists a positive integer k such that every H-free graph has tree width less than k.
It is unfortunate that the value of k in Corollary 1 is generally much larger than the tree width of H (a notable exception is when H = K$_4$, the complete graph on four vertices, for which k = 3). This is one reason that the graph structure theorem is said to describe the "rough structure" of H-free graphs.

### Surface embeddings

Roughly, a surface is a set of points with a local topological structure of a disc. Surfaces fall into two infinite families: the orientable surfaces include the sphere, the torus, the double torus and so on; the nonorientable surfaces include the real projective plane, the Klein bottle and so on. A graph embeds on a surface if the graph can be drawn on the surface as a set of points (vertices) and arcs (edges) that do not cross or touch each other, except where edges and vertices are incident or adjacent. A graph is planar if it embeds on the sphere. If a graph G embeds on a particular surface then every minor of G also embeds on that same surface. Therefore, a "good reason" for G to be H-free is that G embeds on a surface that H does not embed on.
When H is not planar, the graph structure theorem may be looked at as a vast generalization of the Kuratowski theorem. A version of this theorem proved by Wagner (1937) states that if a graph G is both K$_5$-free and K$_{3,3}$-free, then G is planar. This theorem provides a "good reason" for a graph G not to have K$_5$ or K$_{3,3}$ as minors; specifically, G embeds on the sphere, whereas neither K$_5$ nor K$_{3,3}$ embed on the sphere. Unfortunately, this notion of "good reason" is not sophisticated enough for the graph structure theorem. Two more notions are required: clique-sums and vortices.

### Clique-sums

A clique in a graph G is any set of vertices that are pairwise adjacent in G. For a non-negative integer k, a k-clique-sum of two graphs G and K is any graph obtained by selecting a non-negative integer m ≤ k, selecting clique of size m in each of G and K, identifying the two cliques into a single clique of size m, then deleting zero or more of the edges that join vertices in the new clique.
If G$_1$, G$_2$, …, G$_n$ is a list of graphs, then we may produce a new graph by joining the list of graphs via k-clique-sums. That is, we take a k-clique-sum of G$_1$ and G$_2$, then take a k-clique-sum of G$_3$ with the resulting graph, and so on. A graph has tree width at most k if it can be obtained via k-clique-sums from a list of graphs, where each graph in the list has at most k + 1 vertices.
Corollary 1 indicates to us that k-clique-sums of small graphs describe the rough structure H-free graphs when H is planar. When H is nonplanar, we also need to consider k-clique-sums of a list of graphs, each of which is embedded on a surface. The following example with H = K$_5$ illustrates this point. The graph K$_5$ embeds on every surface except for the sphere. However, there exist K$_5$-free graphs that are far from planar. In particular, the 3-clique-sum of any list of planar graphs results in a K$_5$-free graph. Wagner (1937) determined the precise structure of K$_5$-free graphs, as part of a cluster of results known as Wagner's theorem:
Theorem 2. If G is K$_5$-free, then G can be obtained via 3-clique-sums from a list of planar graphs, and copies of one special non-planar graph having 8-vertices.
We point out that Theorem 2 is an exact structure theorem since the precise structure of K$_5$-free graphs is determined. Such results are rare within graph theory. The graph structure theorem is not precise in this sense because, for most graphs H, the structural description of H-free graphs includes some graphs that are not H-free.

### Vortices (rough description)

One might be tempted to conjecture that an analog of Theorem 2 holds for graphs H other than K$_5$. Perhaps it is true that: for any non-planar graph H, there exists a positive integer k such that every H-free graph can be obtained via k-clique-sums from a list of graphs, each of which either has at most k vertices or embeds on some surface that H does not embed on. Unfortunately, this statement is not yet sophisticated enough to be true. We must allow each embedded graph G$_i$ to "cheat" in two limited ways. First, we must allow a bounded number of locations on the surface at which we may add some new vertices and edges that are permitted to cross each other in a manner of limited complexity. Such locations are called vortices. The "complexity" of a vortex is limited by a parameter called its depth, closely related to pathwidth. The reader may prefer to defer reading the following precise description of a vortex of depth k. Second, we must allow a limited number of new vertices to add to each of the embedded graphs with vortices.

### Vortices (precise definition)

A face of an embedded graph is an open 2-cell in the surface that is disjoint from the graph, but whose boundary is the union of some of the edges of the embedded graph. Let F be a face of an embedded graph G and let v$_0$, v$_1$, ..., v$_{n–1}$, v$_n$ = v$_0$ be the vertices lying on the boundary of F (in that circular order). A circular interval for F is a set of vertices of the form {v$_a$, v$_{a+1}$, …, v$_{a+s}$} where a and s are integers and where subscripts are reduced modulo n. Let Λ be a finite list of circular intervals for F. We construct a new graph as follows. For each circular interval L in Λ we add a new vertex v$_L$ that joins to zero or more of the vertices in L. Finally, for each pair {L, M} of intervals in Λ, we may add an edge joining v$_L$ to v$_M$ provided that L and M have nonempty intersection. The resulting graph is said to be obtained from G by adding a vortex of depth at most k (to the face F) provided that no vertex on the boundary of F appears in more than k of the 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 obtained as follows:
* We start with a list of graphs, where each graph in the list is embedded on a surface on which H does not embed
* to each embedded graph in the list, we add at most k vortices, where each vortex has depth at most k
* to each resulting graph we add at most k new vertices (called apices) and add any number of edges, each having at least one of its endpoints among the apices.
* finally, we join via k-clique-sums the resulting list of graphs.
Note that steps 1. and 2. result in an empty graph if H is planar, but the bounded number of vertices added in step 3. makes the statement consistent with Corollary 1.

## Refinements

Strengthened versions of the graph structure theorem are possible depending on the set H of forbidden minors. For instance, when one of the graphs in H is planar, then every H-minor-free graph has a tree decomposition of bounded width; equivalently, it can be represented as a clique-sum of graphs of constant size. When one of the graphs in H can be drawn in the plane with only a single crossing, then the H-minor-free graphs admit a decomposition as a clique-sum of graphs of constant size and graphs of bounded genus, without vortices. A different strengthening is also known when one of the graphs in H is an apex graph.