### L. Consistent cuts

In this part of the appendix, we prove the Consistent Cut Lemma. The lemma says that, under the conditions from the Orientation Lemma, for every context and every recolouring, the context has a cut that is consistent with the recolouring and an orientation from the conclusion of the Bipolar Lemma. We begin by showing that “every” can be replaced by “some”.

**Lemma A.66.** Consider a uniform class of tree decompositions that satisfies the conditions from the Orientation Lemma, and let $\rightarrow$ be one of the two orientations as in the Bipolar Lemma. Then the following are equivalent:

1) for some orientation $\rightarrow$ and recolouring $e$, some context which has a cut that is consistent $\rightarrow$ and $e$;

2) for every orientation $\rightarrow$ and recolouring $e$, every context which has a cut that is consistent with $\rightarrow$ and $e$.

*Proof.* Before continuing with the proof, let us draw attention to a certain distinction. For each context, we associate two similar sets of vertices:

$$ \begin{array}{c} \underbrace{Y \cup X}_{\text{vertices introduced by the context}} \quad \underbrace{\langle Y \rangle \cup \langle X \rangle}_{\text{the interior of the context}} \end{array} \qquad (14) $$

The first set is used to define the unary graph term of a context, while the second set is used to define consistent cuts. The second set is not contained in the first one, because it contains

$$ X \setminus \langle X \rangle \qquad (15) $$

The MSO theory of the above part is always the same, for all nodes. Also, the set (15) has no edges to the rest of $X$, by definition of interiors. It follows from these remarks that the theory of the second set in (14) is uniquely determined by the theory of the first set. Thanks to these remarks, whether or not a context $X \subset Y$ has a cut consistent with an orientation $\rightarrow$ under some recolouring $e$ can be inferred from the theory of the corresponding unary graph term. The following claim discusses how having consistent cuts is preserved when composing unary graph terms.

**Claim A.67.** Consider two unary graph terms $G$ and $H$ that arise from contexts in the tree decomposition. If $G \circ H$ is consistent with $\rightarrow$ under a recolouring $e$, then

* $H$ is consistent with $\rightarrow$ under $e$;

* $G$ is consistent with $\rightarrow$ under $(\text{recolouring of } H) \circ e$.

Suppose now that some unary graph term $G$ in the tree decomposition is consistent with $\rightarrow$ under some recolouring $e$. Consider now some other unary graph term $G$ that appears in the tree decomposition. By uniformity, we know that $G \circ H$ has the same MSO theory as $G$. Since being consistent with $\rightarrow$ under $e$ can be expressed in this theory, it follows that also $G \circ H$ is consistent with $\rightarrow$ under $e$. Therefore, thanks to the above claim, we know that $H$ is also consistent with $\rightarrow$ under $e$. This proves that if some context in the tree decomposition is consistent with $e$, then all other contexts

have this property. Let us now show that $e$ is unimportant. Take some recolouring $f$, which is represented by some unary graph term $F$. We know that $F \circ F$ must be consistent with $\rightarrow$ under $e$, since $F$ is consistent with $\rightarrow$ under $e$, and its theory is idempotent. Therefore, by the above claim it follows that $F$ is consistent with $\rightarrow$ under $f \circ e = f$. $\square$

*Proof of the Consistent Cut Lemma.* Choose a recolouring $e$ so that

$$ T_e \stackrel{\text{def}}{=} \{T \mid \begin{array}{l} T \text{ is a sub-decomposition of } \mathcal{T} \text{ where} \\ \text{all contexts have recolouring } e \end{array} \} $$

has unbounded Strahler number, which can be done thanks to Lemma A.10. By Lemma A.66, every context in $\mathcal{T}$ has a cut consistent with $\rightarrow$ if and only if the same is true for $T_e$. Therefore, it is enough to prove the present lemma in the case where all contexts have the same recolouring $e$. From now on, we assume that $\mathcal{T}$ has a unique recolouring. This means that for each supercolour $A$, there is a unique fixpoint colour $e(A)$, which we will call the fixpoint colour of $A$.

As in the Bipolar Lemma, we will show that every violation of the conclusion of the lemma will be witnessed by some patterns in contexts, which in turn can be used to apply the Covering Lemma.

As discussed after Definition V.13, for each context there is at most one possible cut, up to the placement of connected components that use only local colours. Therefore, it remains to show that this only candidate is indeed correct. We begin by introducing some notation to describe the candidate. Define the *interior* of a context $X \subset Y$ to be the set

$$ U = \langle Y \rangle \cup \langle X \rangle $$

that is used in the definition of a consistent cut in a context.

**Definition A.68.** Let $v$ be a vertex with a non-local super-colour $A$, which is in the interior of a context $X \subset Y$. We say that $v$ is on the left side with respect to some supercolour $B$, with fixpoint colour $b$, such that:

* $A \rightarrow B$ and there is an edge from $v$ to $X.b$; or

* $A \leftarrow B$ and there is no edge from $v$ to $X.b$.

Analogously, we say that $v$ is on the right side with respect to supercolour $B$ with fixpoint colour $b$ if:

* $A \rightarrow B$ and there is no edge from $v$ to $X.b$; or

* $A \leftarrow B$ and there is an edge from $v$ to $X.b$.

We say that $v$ is on the left side if it is on the left side with respect to some supercolour; likewise for the right side.

The above definition assigns a side to every vertex in a non-local colour. As far as we know, a vertex could end up on both the left side and on the right side; this is something that we will need to exclude. There could be other problems with having a consistent cut, e.g. there could be vertices on two different sides which are connected by an edge that violates condition 6 of Definition V.12. The following claim gives a complete list of such problems.
**Claim A.69.** A context $X \subset Y$ does not have a cut consistent with $\rightarrow$ and the recolouring $e$ if and only if one of the following conditions is satisfied:

1) There is a vertex $v$ in the interior of the context which has a non-local supercolour and such that:

a) $v$ is on the left side with respect to some supercolour; and

b) $v$ is on the right side with respect to some supercolour.

2) There are vertices $v \neq w$ in the interior of the context which have non-local supercolours and such that:

a) $v$ is on the left side with respect to some supercolour; and

b) $w$ is on the right side with respect to the same super-colour; and

c) the equivalence from Definition V.12 is violated.

3) There is a path where all vertices are in the interior of the context and:

a) the internal vertices (i.e. the vertices that are not the source or target of the path) have local colours;

b) the source is on the left side with respect to some supercolour;

c) the target is on the right side with respect to some supercolour.

*Proof.* The proof of this claim is essentially the same reasoning as in our comments after Definition V.13, which explained that the cut is unique if it exists, up to connected components that contain only local colours.

The problem in item 1 shows that it is impossible to assign sides to vertices with non-local colours while satisfying condition 2 of Definition V.13. Therefore, if this problem arises, there cannot be a consistent cut. On the other hand, if this problem does not arise, then to each vertex with a non-local colour we can assign uniquely a side, which is the only possible side that can be used in cut as in Definition V.13.

Suppose now that the problem from item 2 arises. This means that the assignment of sides for vertices with non-local colours violates the equivalence in Definition V.12. Therefore, if this problem arises, then there cannot be a consistent cut. Otherwise, if the problems from items 1 and 2 do not arise, the unique assignment of sides for vertices with non-local colours satisfies all conditions of a consistent cut for such vertices.

Finally, the problem from item 3 is used to extend the cut to vertices with local colours. If this problem arises, then there is no way to assign sides to vertices with local colours that appear on the path from the problem, since the equivalence in Definition V.12 would require that all vertices on this path have to be on the same side. On the other hand, if this problem, and the ones before it, does not arise, then one can assign a side to each vertex with a local colour that is connected by a path to some non-local colour; this assignment will be unambiguous because the problems 3 does not arise.

Finally, as mentioned before, for vertices with local colours that are not connected to any non-local colour, we can assign sides arbitrarily. □

To complete the proof of the lemma, we will show that if any of the problems from the above claim arise, then some obstruction is covered, and the Covering Lemma can be used to contradict the assumption of the lemma. Therefore, none of the problems can arise, and so there is a consistent cut.

**Problem 1:** We begin with the problem where some vertex with a non-local colour is on both sides at the same time. Consider such a vertex $v$ that witnesses this problem, and let $A$ be its supercolour. This supercolour is non-local, by the definition of Problem 1.

Recall the distinction between $Y \setminus X$ and $\langle Y \rangle \setminus \langle X \rangle$ that was discussed in (14). For the vertex $v$ this distinction is irrelevant, i.e.

$$v \in Y \setminus X \Leftrightarrow v \in \langle Y \rangle \setminus \langle X \rangle.$$

This is because $v$ has a non-local colour, and therefore it cannot belong to $X \setminus \langle X \rangle$.

There is a reason why $v$ is on the left side, namely there is some supercolour $B_1$, with fixpoint colour $b_1$, such that:

1) $A \rightarrow B_1$ and there is an edge from $v$ to $X.b_1$; or

2) $A \leftarrow B_1$ and there is no edge from $v$ to $X.b_1$.

Because $v$ is on the right side, there is some $B_2$ with fixpoint colour $b_2$, such that:

1) $A \rightarrow B_2$ and there is no edge from $v$ to $X.b_2$; or

2) $A \leftarrow B_2$ and there is an edge from $v$ to $X.b_2$.

Clearly the two fixpoint colours cannot be equal. Let us first observe that we can assume without loss of generality that we only need to look witnesses for the problem that use fixpoint colours.

**Claim A.70.** *Without loss of generality, we can assume that the colour of $v$, with respect to the node $Y$, is the fixpoint colour $a \in A$.*

*Proof.* If we compose the context with itself, then we get a witness in a fixpoint colour. □

There could be two orientations between $A$ and $B_1$, and also two orientations between $A$ and $B_2$. This leads to four possible cases, which are similar. To reduce the number of cases, we use an argument that flips supercolours, as described in the following claim (which chooses a case that will be best for pictures):

**Claim A.71.** *We can assume without loss of generality that $B_1 \rightarrow A \rightarrow B_2$.*

*Proof.* Suppose that we flip two entangled supercolours in the class. The result will be that the orientation of these two supercolours will flip directions. Otherwise, the assumptions of the lemma, and also its conclusions, will not be affected. This is because flipping supercolours does not affect uniformity, existence of consistent cuts, or transducing all trees. □
Assume the orientation from the above claim. This means that the witness $v$ for the problem is connected to neither $b_1$ nor $b_2$. (It is also not connected to $a$, since otherwise $A$ would be entangled with itself.) Here is a picture of the witness for the problem:

<figure><img src="image_59.png" /></figure>

Using the same argument as in Claim A.71, we can assume without loss of generality that if $B_1$ and $B_2$ are entangled, then they are oriented in the direction $B_1 \to B_2$. This means that for every disjoint nodes $X_1$ and $X_2$, the connections between colours $b_1, a, b_2$ look like this:

<figure><img src="image_60.png" /></figure>

Consider a separated bicontext $X_1, X_2 \subset X$ in the class, with a separating node $Y$. The pattern from Picture 5 appears in the context $Y \subset X$, and the pattern from Picture 4 appears between the nodes $X_1$ and $X_2$. This shows that the bicontext covers one of the following binary graph terms, depending on whether $B_1$ is entangled with $B_2$:

<figure><img src="image_61.png" /></figure>

These terms were proved to be obstructions in Claim A.60. Therefore, we can apply the Covering Lemma to show that $\mathcal{T}$ covers a regular branching class. Since this contradicts the assumption of the lemma, it follows that problem 1 cannot arise.

**Problem 2:** We now consider the problem where there are two witness vertices that are on different sides, but their connection (edge or non-edge) violates the equivalence in Definition V.12. Since these vertices use non-local supercolours, the same remarks as for Problem 1 show that they cannot belong to $X$. Each of these two witness vertices has its own supercolour, and there is another entangled supercolour that is used to assign a side. Therefore, there are up to four supercolours involved, some of which may be equal to each other. We study the different cases, in increasing order of the number of supercolours that are involved in the analysis.

1. Suppose first that the two witness vertices have the same supercolour. This means that there are only two supercolours involved: the supercolour $A$ of the two vertices, and some other entangled supercolour $B$ that is used to assign the vertices to their sides. Assume without loss of generality that $A \to B$. Let $v$ be the vertex on the left side, and let $w$ be the vertex on the right side. Since the supercolour $A$ cannot be entangled with itself, it follows that a violation of condition 6 must consist of an edge from $v$ to $w$. As in Claim A.70, we can assume without loss of generality that both $v$ and $w$ have the fixpoint colour $a \in A$. This means that every context witnesses a pattern like this:

<figure><img src="image_62.png" /></figure>

Combining this with the assumption that $A \to B$, we see that every separated bicontext covers the following term:

<figure><img src="image_63.png" /></figure>

his term can be shown to be an obstruction using the same argument as in Claim A.60, and therefore the problem cannot arise.

2. Suppose now that the two witness vertices have different supercolours, $A$ and $B$, but these supercolours are entangled, with the corresponding orientation being $A \to B$. By flipping edges as in Claim A.71, we can assume without loss of generality that the vertex on the left side has supercolour $A$ and the vertex on the right side has supercolour $B$. This means that every context contains the following pattern:

<figure><img src="image_64.png" /></figure>

This in turn means that every separated bicontext covers the following term:

<figure><img src="image_65.png" /></figure>

The problem with this term is that we are missing the edge between the two vertices introduced by it. Again, this term is an obstruction, and therefore the corresponding problem cannot arise.

3. Suppose now that the two witness vertices have different supercolours $A$ and $B$, which are not entangled. Suppose first that there is third supercolour $C$ that is entangled
with both of them. As in Claim A.71, we assume without loss of generality that $B \to C \to A$. Using the same reasoning as above, we see that every separated bicontext covers the following term:

<figure><img src="image_66.png" /></figure>

Again, this term is obstruction, and therefore the corresponding problem cannot arise.

4) Finally, consider the case that all four supercolours (the two supercolours of the witness vertices, and the two entangled supercolours that are used to assign sides) are different. In this case, we can use the same reasoning as above to show that every separated bicontext covers one of the following two obstructions:

<figure><img src="image_67.png" /></figure>

**Problem 3:** Finally, let us consider the last problem from Claim A.69, which discusses local colours. In this problem, there is a path that uses local colours internally, and whose endpoints have non-local colours on different sides. This path is contained in $\langle Y \rangle \setminus \langle X \rangle$. Unlike the previous problems, the witness here might overlap with $X$, since it the path might pass through vertices from $X \setminus \langle X \rangle$. Let us begin by showing that this path cannot go very deep inside the context $X$. This is because, thanks to the following claim, the set $X \setminus \langle X \rangle$ cannot overlap with any child of $X$.

**Claim A.72.** For every context $X \subset Y$, we have $X \subseteq \langle Y \rangle$.

*Proof.* This is because in the graph induced by $Y$, the set $X$ is contained in a single connected component, which follows from colour connectedness. $\square$

Therefore, we know that the path which witnesses Problem 3 cannot overlap with any children of $X$. The following claim shows that we can assume without loss of generality that it uses fixpoint colours, from the perspective of the node $Y$.

**Claim A.73.** Without loss of generality, we can assume that all colours used by the witnessing path are fixpoint colours.

*Proof.* Same argument as in Claim A.70. $\square$

As in the case of Problem 2, we study the non-local supercolours $A$ and $B$ of the endpoints in the witnessing paths, and the supercolours entangled with them that are

used to assign sides to the endpoints. This leads to up to four non-local supercolours under consideration, plus the local colour $\ell$ used for the path as Claim A.73. The analysis is the same as in the case of Problem 2, so we only do the first case (when $A = B$) to show how local colours are used, and leave the remaining cases to the reader.

Suppose that the witnessing path for the problem has both endpoints in the same supercolour $A$. Let $a$ be the fixpoint colour in $A$. This means that for every context we can find a path from $a$ to $a$, which uses local colours internally. Choose some supercolour $B$ that is entangled with $A$, say oriented as $A \to B$, which will be used to assign sides to vertices from $A$. Since a witnessing path can be found in every context, it follows that every separated bicontext can find a path as in the following picture:

<figure><img src="image_68.png" /></figure>

(The fact that this path does not overlap with the two arguments of the multicontext is a corollary of Claim A.72.) By contracting the local colours on the path to a single vertex, which is allowed for covering, we see that every separated bicontext covers the following term:

<figure><img src="image_69.png" /></figure>

This term is branching, for the same reasons as for the previous terms considered in this proof, and therefore such a problem cannot arise.

As mentioned before, there are several reasons for why the non-local supercolours $A$ and $B$ are on different sides, which correspond to the four cases 1-4 studied for Problem 2. Above we have studied the first case, which gave a local analogue of the obstruction from item 1 in Problem 2. The reasoning in the remaining cases, which correspond to items 2-4, is the same. In each case we get a single contracted vertex, in a local fixpoint colour, which is connected to two vertices that have non-local fixpoint colours, and are on different sides. Each such situation leads to covering an obstruction, and thus the corresponding problems cannot arise. We leave the proof to the reader, but we only give the corresponding obstructions. In each case the obstruction arises by taking an obstruction from Problem 2, and subdividing the anomalous edge (the one which contains two vertices introduced in the obstruction) with a local colour.
The obstruction corresponding to item 2 in Problem 2 is:

<figure><img src="image_70.png" /></figure>

The obstruction corresponding to item 3 in Problem 2 is:

<figure><img src="image_71.png" /></figure>

The obstructions corresponding to item 4 in Problem 2 are

<figure><img src="image_72.png" /></figure>

### M. Proof of the Dichotomy Lemma

<figure><img src="image_73.png" /></figure>

In this part of the appendix, we complete the proof of the Dichotomy Lemma, by showing Lemma V.15, which says that the Dichotomy Lemma holds for classes of tree decompositions that satisfy the conditions from the Orientation Lemma.

*Proof of Lemma V.15.* Apply the Bipolar Lemma to get an orientation $\rightarrow$ that is unique, up to taking opposites. Fix this orientation for the rest of the proof.

The proof proceeds in three stages. In the first stage, we show that orientations of nodes do not depend on recolourings. In the second stage, we use the orientations to describe a linear order on nodes in a tree decomposition. In the third and final stage, we use this linear order to define linearisations.

**Stage 1. Orientations do not depend on recolourings:**

Recall that in an oriented class of tree decompositions, an orientation arises for every choice of

$$ \underbrace{(X_1, e_1)}_{\text{node and recolouring}} \quad \text{and} \quad \underbrace{(X_2, e_2)}_{\text{node and recolouring}} $$

where the two nodes are disjoint. The first stage of the proof shows that the orientation does not depend on the

recolourings $e_1$ and $e_2$, but only on the nodes $X_1$ and $X_2$. This will be a surprisingly long argument.

In the notion of consistent cut from Definition V.12, we partitioned vertices from a set $U$ across two sides. Below, we will be interested in the case when the set $U$ is a node, and the partition depends only on colours of the node. Suppose that the tree decompositions use $k$ colours, and let

$$ \kappa: \{1, \dots, k\} \rightarrow \{\text{left, right}\} $$

be a function that assigns a side to every colour. For each node $X$, this partition can be used to split the vertices in the node into two sides, according to their colours in the node. Such a partition is called a *colour cut for node $X$* if the corresponding partition on vertices in the node is a cut consistent with the orientation $\rightarrow$, as per Definition V.12. Whether or not a partition of the colours is a colour cut for a node $X$ is expressible in MSO, with low quantifier depth. Since all nodes have the same theory, it follows that the partition $\kappa$ is either colour cut for every node, or for no nodes. Therefore, we do not need to indicate the node, and we can simply speak of a partition of the colours as being a colour cut or not.

Our proof strategy for stage 1 is to show that if the orientation would depend on the recolourings, then there would be a non-trivial colour cut, and such a colour cut could be used to apply the induction assumption in the Dichotomy Lemma to reduce the width of the tree decomposition.

The following claim shows that colour cuts cannot split images of recolourings.

**Claim A.74.** If $\kappa$ is a colour cut, then for every recolouring $e$, all colours in the image of $e$ are on the same side.

*Proof.* Consider a unary graph term $E$, which arises from some context in the class of tree decompositions, and which has recolouring $e$. Let $G_0$ be any graph the class, and define

$$ G_{n+1} = E \circ G_n $$

to be the graph that results of applying $E$ to $G_n$. By uniformity, we know that all the graphs $G_n$ have the same MSO theory of low quantifier depth.

Let $A$ and $B$ be entangled supercolours. From entanglement, it follows that $G_1$ has an edge between $A$ and $B$, and also a non-edge between $A$ and $B$. It follows that $G_2$ has an edge between $e(A)$ and $e(B)$, and also a non-edge between these two colours. It follows that these two colours must be on the same side of the cut corresponding to $\kappa$ in $G_2$. This implies that if $A$ and $B$ are in the same connected component of the entanglement graph, then $e(A)$ and $e(B)$ must be on the same side of the colour cut.

Consider now $G_1$, and an edge in this graph where both endpoints are from $G_0$. If the supercolours of the two endpoints are not entangled with each other, then both endpoints must be on the same side of the cut corresponding to $\kappa$ in $G_1$. If both endpoints have entangled colours, then the argument from the previous paragraph shows that the two endpoints must be on the same side of the cut. Summing up, we have
shown that every connected component of the graph $G_0$ is on the same side of the cut. Some such connected component touches all colours, by the colour connectedness property, and therefore all colours in the image of $e$ are on the same side. $\square$

Consider a tree decomposition in $T \in \mathcal{T}$, and let $\kappa$ be a colour cut that is non-trivial, which means that not all vertices are on the same side. For each node, apply the colour cut, giving a partition of the node into two sides, the left side and the right side. By Claim A.74, every child of the node is contained in either the left side, or the right side. Therefore, if we consider the family of subsets

$$T' = \{\text{root}\} \cup \{\text{left side of } X, \text{right side of } X \mid X \in T\},$$

then the family satisfies the hierarchical condition in the definition of a tree, and hence can be seen as a new tree decomposition. The following claim shows that the new tree decomposition has strictly smaller width.

**Claim A.75.** Consider a non-trivial colour cut $\kappa$. For every node $X$, its rank is strictly bigger than the rank of its left side (with respect to $\kappa$). Likewise for the right side.

*Proof.* Consider a node $X$, and its partition

$$X_{\text{left}} \cup X_{\text{right}}$$

that arises from the cut. We will show that the contextual classes of the left side $X_{\text{left}}$ are the same as the contextual classes of $X$ (i.e. the colours of $X$) that are on the left side of the cut. This will imply that the rank of the left side is strictly smaller than the rank of $X$, because not all colours are used. Consider a colour $a$ that is on the left side of the cut $\kappa$. If we take two vertices from $X.a$, then they have the same connections to the complement of $X$, by definition of colours in a tree decomposition. Also, these two vertices will have the same connections to vertices on the right side of $X$. This is because for consistent cuts, the presence or absence of an edge for a pair of vertices on different sides is determined by their supercolours. $\square$

Putting the above two claims together, we conclude that if there is a non-trivial colour cut, then we can reduce the width of the tree decomposition, and thus use the induction assumption on width to prove the Dichotomy Lemma. Therefore, it remains to prove the Dichotomy Lemma under the assumption that there is no non-trivial colour cut. We assume this for the rest of the proof. The following claim shows that under this assumption, we can finally remove the dependence on recolourings from orientations, thus completing stage 1 of the proof.

**Claim A.76.** Assume that there is no non-trivial colour cut. Then for every disjoint nodes $X_1$ and $X_2$, the orientation of

$$(X_1, e_1) \text{ and } (X_2, e_2)$$

does not depend on the choice of the recolouring.

*Proof.* Consider the context $X_1 \subset \text{root}$, and a cut $\kappa$ in this context that is consistent with the orientation $\to$ and some recolouring $e_1$. For vertices from $X_2$, their side with respect to the cut $\kappa$ depends only on their colours. Therefore, all vertices from $X_2$ must be on the same side of the cut, since otherwise we would get a non-trivial colour cut. Consider some two entangled supercolours $A_1$ and $A_2$. Since all vertices from $X_2$ are on the same side of the cut $\kappa$, it follows that all vertices in $X_2.A_2$ have the same connection to $X_1.a_1$, where $a_1$ is the image $e_1(A_1)$. This is because the kind of connection (edge or non-edge) is uniquely determined by the condition 2 in Definition V.13. This implies that the orientation in the statement of the claim does not depend on the choice of $e_2$. A similar argument works for $e_1$, thus proving the claim. $\square$

**Stage 2.** A liner order: We now proceed to the second stage of the proof, where we define the linear preorder that will be the basis of our linearisation. Thanks to Claim A.76, for every disjoint nodes $X_1$ and $X_2$, there is an orientation, which does not depend on the choices of recolourings. This orientation is either the orientation $\to$ that we have fixed at the beginning of the proof of this lemma, or its opposite. We write $X_1 < X_2$ in the first case, and $X_1 > X_2$ in the second case. The following claim justifies the order notation.

**Claim A.77.** The relation $<$ is a linear order on every antichain of nodes.

*Proof.* By the Biopolar Lemma, the only two possible orientations are $\to$ and its opposite. Therefore, every two disjoint nodes are related by the relation in some direction. It remains to prove that the relation is transitive. A violation of transitivity would consist of a cycle of length three for this relation. Take the middle node in this cycle, and consider two entangled supercolours $A$ and $B$. From the perspective of the middle node, colour $A$ of the first node in the cycle belongs to the left part (as in Definition V.13), and colour $B$ of the third node in the cycle belongs to the right part. However, because of the cycle, there is an edge connecting these colours, which leads to a violation of consistent cuts. $\square$

We use the name sequential order for the order $<$. The following claim shows that the sequential order is compatible with the descendant relation.

**Claim A.78.** If $X_1 < X_2$ and $Y_1 \subset X_1$, then $Y_1 < X_2$.

*Proof.* Let $e$ be the recolouring of $Y_1 \subset X_1$. The orientation of

$$(Y_1, e) \text{ and } (X_2, e)$$

is equal to the orientation of

$$(X_1, e) \text{ and } (X_2, e).$$

So far, we have only ordered nodes between each other. We will now extend the order so that we can compare an
individual vertex to a node. For the rest of this proof, choose some recolouring e. The choice of recolouring will not matter.

**Definition A.79** (Sides of a node). Consider a node X and a vertex

$$v \in \langle \text{root} \rangle \setminus \langle X \rangle$$

We say that v is on the left side of X, denoted by $v < X$, if v is on the left side of every cut in the context $X \subset \text{root that is consistent with the orientation } \rightarrow$ and the fixed recolouring e. Analogously we define the right side and $X < v$.

According to the above definition a vertex $v \notin X$ might be neither on the left nor right side of X. This will happen if for some cuts v is on the left side, and for other cuts v is on the right side. The situations where this can happen were discussed after Definition V.13.

**Claim A.80.** Consider disjoint nodes $X_1 < X_2$. Then

$$v < X_1 \Rightarrow v < X_2 \quad \text{for every vertex v.}$$

*Proof.* Before proving the claim, we clarify one issue. The definition of $v < X$ requires that the vertex v is not in the interior of the node X. Therefore, the assumption of the implication implies that v is not in the interior of $X_1$, and the conclusion of the implication implies that v is not in the interior of $X_2$.

We begin with the case when v has a non-local colour. Choose some cut $\kappa$ in the context $X_1 \subset \text{root that is consistent with the orientation } \rightarrow$ and the chosen recolouring e. By definition of $v < X_1$, we know that v is on the left side of this cut, while by $X_1 < X_2$ we know that all vertices with fixpoint colours in $X_2$ are on the right side of this cut. In particular, v cannot belong to $X_2$. Let A be the supercolour of v, let B be some entangled supercolour. By definition of consistent cuts, there is only one possible choice for the edge relation between v and vertices with colour from B on the other side of the cut, and this choice is such that it implies $v < X_2$.

Consider now the case when v has a local colour. A consequence of $v < X_1$ is that there is a path where:

1) the source is v;

2) the target, call it w, has non-local colour and $w < X_1$;

3) all vertices from the path, except its source and target, use local colours and are not in the interior of $X_1$.

By the case of non-local colours that was discussed in the previous paragraph, we know that w also satisfies $w < X_2$. To finish the proof, we will show that the path described above avoids the interior of $X_2$, and therefore it also witnesses $v < X_2$. Otherwise, some prefix of this path would link v with the interior of $X_2$. By definition of the interior, this prefix could be extended so as to reach a vertex with non-local colour in $X_2$, while still avoiding the interior of $X_1$. This way we would get a path connecting the left and right sides of the cut $\kappa$, and using only local colours internally. This would violate the consistency of the cut $\kappa$. □

**Stage 3. A linearisation:** We now proceed to the third and final stage of the proof, where we use the orders above to define linearisations.

Consider a tree decomposition $T \in \mathcal{T}$. In the rest of this proof, we will define a linearisation for this tree decomposition, which has bounded width. This means that the width will be bounded by a constant that depends only on $\mathcal{T}$, and not on the tree decomposition.

When defining the linearisation, we will only be interested in the vertices that are in the interior of the root node. The remaining vertices are all introduced in the root node by Claim A.72, and they do not have any edges to the interior of the root node. Therefore, we can place them at the beginning of the linearisation, or in any other place, without affecting its width. From now on, we only consider the vertices that are in the interior of the root node.

Let the leaves of the tree decomposition be

$$X_1 < \dots < X_n,$$

listed according to the canonical order that was defined in the second stage. In our linearisation, the interior of each leaf will be a single part. The remaining vertices to be are linearised are those which are in the interior of the root node, but not in the interior of any of the leaves, i.e.

$$U \stackrel{\text{def}}{=} \langle \text{root} \rangle \setminus ((X_1) \cup \dots \cup (X_n)).$$

To arrange the vertices from U in the linearisation, we will compare them to the leaf nodes. To simplify notation, we use the following convention for edge cases:

$$X_0 < v \stackrel{\text{def}}{=} \text{true} \quad v < X_{n+1} \stackrel{\text{def}}{=} \text{true.}$$

The following claim is the basis for the arrangement of vertices from U in the linearisation.

**Claim A.81.** For every vertex $u \in U$ there is exactly one $i \in \{0, 1, \dots, n\}$ such that

$$X_i < u < X_{i+1}.$$

*Proof.* A straightforward consequence of Claim A.80. □

For $i \in \{0, 1, \dots, n\}$, define $U_i$ to be the vertices where the index from the above claim is i. The following claim shows that vertices from $U_i$ can only be introduced in certain parts of the tree decomposition.

**Claim A.82.** Consider a vertex $u \in U_i$, and let X be its *introducing node*. Then the parent of X, call it Y, is an ancestor of at least one of the nodes $X_i$ and $X_{i+1}$.

*Proof.* Let us begin with a clarification. In the statement of the claim, in the edge case where $i = 0$ or $i = n$, then only one of the nodes $X_i$ or $X_{i+1}$ is defined, and then Y must be an ancestor of that node.

Toward a contradiction, suppose that Y is not an ancestor of any of the two leaves, which means that it is disjoint with both of them. Since all three nodes are disjoint, we can compare them using the canonical order. The node Y cannot
be between $X_i$ and $X_{i+1}$, by definition of consecutive leaves and Claim A.78. Therefore, $Y$ is on the same side of both $X_i$ and $X_{i+1}$. By symmetry, we assume

$$X_i < X_{i+1} < Y.$$

By Claim A.72, we know that $u$ is in the interior of $Y$. By Claim A.80 and the assumption that $u < X_{i+1}$, we know that $u < Y$, and therefore $u$ cannot belong to the interior of $Y$. This is a contradiction. □

We use the claim above to show that the vertices between $X_i$ and $X_{i+1}$ admit a linearisation of bounded width.

**Claim A.83.** Let $i \in \{0, 1, \dots, n\}$. The tree decomposition $T$ restricted to $U_i$ admits a linearisation of bounded width.

*Proof.* Let $B_i$ be the branch in the tree decomposition which consists of ancestors of node $X_i$. By Claim A.82, we know that every vertex in $U_i$ introduced in a node that is either in one of the branches $B_i$ or $B_{i+1}$, or a sibling of such a node. Using the assumption that all local sub-decompositions have linearisations of bounded width, we can linearise the vertices from $U_i$ by traversing the two branches in bottom-up order. □

We are now ready to finish the proof. Consider the sets $U_i$ from the above claim. By Claim A.81, we know that every vertex in the interior of the root node belongs either to some $U_i$, or to the interior of some leaf. Consider the linear preorder

$$U_0 < \langle X_1 \rangle < U_1 < \langle X_2 \rangle < \dots < U_{n-1} < \langle X_n \rangle < U_n. \quad (16)$$

Like any preorder, the above can be seen as a linear tree decomposition. We will show that it has bounded width, i.e. prefixes have bounded rank.

**Claim A.84.** The linear tree decomposition described in (16) has bounded width.

*Proof.* Consider a partition of the linear preorder into a prefix and a suffix. We assume that the prefix ends with the interior of some node, say $\langle X_i \rangle$. (The other case is when the suffix begins with the interior of some node; this case is symmetric.) For vertices in the suffix, their relation to the parts strictly before $\langle X_i \rangle$ are entirely determined by supercolours, since they are on a different side of a consistent cut in $X_i \subset \text{root}$. The relation of the suffix with $X_i$ is entirely determined by the colour of the vertex from $X_i$. Summing up, the rank is bounded by a function of the number of colours. □

In the linear preorder from (16), we can now replace each part $U_i$ by its linearisation from Claim A.83. The result will be a linearisation of bounded width, thus completing the proof of the lemma. □