# Tangles and a Structure Theorem

The result that we discuss here is Theorem 2.1 in Kawarabayashi and Wollan’s article, originally (3.1) in Graph Minors XVI, which plays a bigger role in the subsequent proof of the graph minor theorem than the “cornerstone” Graph Decomposition Theorem, and which indeed is used in the proof of said decomposition theorem.

This structure theorem states that given a $H$-minor-free graph $G$, for every tangle $\mathcal{T}$ in $G$ of order $\geq \theta$, there exists $A \subset V(G)$ of size at most $\alpha$ such that $G - A$ has an $\alpha$-bounded $\alpha$-near embedding into a surface $\Sigma$ into which $H$ cannot be embedded, and this near-embedding captures $\mathcal{T} - A$.

Here capturing the tangle means that we can find a $(\mathcal{T} - A)$-central segregation $\mathcal{S}$ of $G - A$ (i.e. a partition $\mathcal{S}$ of $G - A$ into edge-disjoint societies such that no society in $\mathcal{S}$ contains the large side of any separation in $\mathcal{T}$) with a bounded number of large vortices and vortex decompositions of bounded depth in our near-embedding.

What is a tangle?

A tangle $\mathcal{T}$ of order $\theta$ is a set of ordered separations $(A,B)$ such that for every separation $\{A, B\}$ of $G$ of order $\leq \theta$, either $(A,B)$ or $(B,A)$ is in $\mathcal{T}$, and such that $G[A_1] \cup G[A_2] \cup G[A_3] \neq G$ for any $(A_i, B_i) \in \mathcal{T}$ with $i=1, 2, 3$. In short, a tangle is a “complete” (in the sense of the first axiom) set of small-order separations which leave a substantial part of the graph on the $B$ side (in the sense of the second axiom.)

From the Structure Theorem to the Graph Decomposition Theorem

The structure theorem here plays a key role in Kawarabayashi-Wollan’s proof of the Graph Decomposition Theorem (which is essentially the same as Robertson-Seymour’s proof [?].)

Recall our last restatement of the Graph Decomposition Theorem; this we will prove by induction on $|V(G)|$. The structure theorem gives us (positive) constants $\hat{\theta}$ and $\hat{\alpha}$ such that, for every tangle of order $\geq \hat{\theta}$, $G$ is $\hat\alpha$-close to having an $\alpha$-bounded $\hat\alpha$-near embedding into a surface $\Sigma$ into which $H$ does not embed, and this near-embedding $H_0, H_1, \dots, H_m$ captures $\mathcal{T}$.

Choose $\theta = \max(\hat\theta, 3\hat\alpha+1)$ and $\alpha := 4\theta - 2$ ($\theta$ is chosen so that $3 + \hat\alpha \leq \theta$ and $\hat\theta \leq \theta$ hold, and $\alpha$ so that $3\theta - 1 \leq \alpha$). For the base case, we observe that we may assume $|V(G)| \geq \alpha$, otherwise the result is trivially true.

We now induct by decomposing each vortex $H_i$ in our near-embedding separately and putting the pieces together. The exceptional subgraph $H_0$ can be left as is; the small vortices can be split along society vertices; the large vortices can be split along vortices of the parts of its vortex decomposition (see p.9 of Kawarabayashi and Wollan for details); inductively we obtain the desired tree-decompositions for each smaller part, and then piece them together by connecting one of their vertices to the new root $v_0$ (representing $latex G[V(H_0) \cup \hat{A}$), we may check that the torso of the new part $V_0$ can be $\alpha$-nearly embedded as desired.