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 = K4, 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 K5-free and K3,3-free, then G is planar. This theorem provides a "good reason" for a graph G not to have K5 or K3,3 as minors; specifically, G embeds on the sphere, whereas neither K5 nor K3,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 G1, G2, …, Gn 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 G1 and G2, then take a k-clique-sum of G3 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 = K5 illustrates this point. The graph K5 embeds on every surface except for the sphere. However, there exist K5-free graphs that are far from planar. In particular, the 3-clique-sum of any list of planar graphs results in a K5-free graph. Wagner (1937) determined the precise structure of K5-free graphs, as part of a cluster of results known as Wagner's theorem: Theorem 2. If G is K5-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 K5-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.
… excerpt ends here. Continue reading the full article.
