# On the Descriptive Complexity of Color Coding +
## 4 Syntactic Proofs and Natural Problems
### Bounded Strong-Rank Description of Embedding Graphs of Constant Tree Width or Constant Tree Depth
For each new element \(e\), let \(p(e)\) be a different number from the set \(\{1,\ldots,m\}\setminus\{p(v)\mid v\in B(r)\cap B(c)\}\) and note that we will not run out of numbers. We assign numbers to all elements in the bags of the children of the root in this way and, then, we recursively use the same method for the children's children and so on. Note that, not only, we do not run out of numbers, but the consistency condition is also met: Once an element drops out of a bag, we will never see it again in a later bag and, hence, we cannot inadvertently assign a different number to it later on. As a running example, we will use the graph \(H\) and the tree decomposition \((T,B)\) of it from Figure 1.  
Let us now define \(\phi_{H,T,B}\). We may assume \(V(H)=\{1,\ldots,|V(H)|\}\). The first step is to bind all vertices of \(H\) to weak variables using \(\exists\hat{x}_{1}\cdots\exists\hat{x}_{|V(H)|}\bigwedge_{i\
eq j}\hat{x}_{i} \
eq j_{j}\wedge\psi\), where \(\psi\) must now express that the bound elements form an embedding. To achieve this, we build \(\psi\) recursively, starting at the root \(r\) of \(T\) and \(\psi=\psi_{r}\). For our example, we would have:  
\[\phi_{H,T,B}=\exists\hat{x}_{1}\cdots\exists\hat{x}_{7}\bigwedge_{i\
eq j}\hat{ x}_{i}\
eq\hat{x}_{j}\wedge\psi_{r}.\]  
For any node \(n\in V(T)\), let the elements of the set \(B(n)\) be named \(b_{1}\) to \(b_{s}\) (these are just temporary names that have nothing to do with the consisting numbering \(p\)) and let the first \(t\) of them be new, that is, not present in the parent bag (for the root, \(s=t\) and all elements are new; if there are no new elements, \(t=0\)). The formula \(\psi_{n}\) will now express the following: First, it binds the new elements using strong variables that are made equal to the weak variables representing the elements in the input structure. This makes the new strong variables disjoint from one another and also from all other (images of) vertices of \(H\). Second, we check that for all edges \(\{x,y\}\in E(H)\) between elements \(x\) and \(y\) of \(B(n)\), that their images (which we have bound to strong variables) are also connected in the input structure. Third, we require that these properties also hold for all children of \(n\). In symbols, we set:  
\[\psi_{n}=\exists v_{p(b_{1})}\cdots\exists v_{p(b_{t})} (v_{p(b_{1})}=\hat{x}_{b_{1}}\wedge\cdots\wedge v_{p(b_{t})}=\hat{x}_{b_{t}}\wedge\] \[\bigwedge_{x,y\in B(n),\{x,y\}\in E(H)}Ev_{p(x)}v_{p(y)}\wedge\] \[\bigwedge_{c\in\text{children}(n)}\psi_{c}).\]  
For our example, let us start with the root \(r\). Here, we have \(B(r)=\{3\}\) and \(p(3)=1\) and there are no edges between the vertices in the bag (there is just one vertex, after all). This yields: \(\psi_{n}=\exists v_{1}(v_{1}=\hat{x}_{3}\wedge\psi_{a}\wedge\psi_{b})\). For the node \(a\), a new node (1) enters the bag \(B(a)\) with index \(2=p(1)\), but there are no intra-bag edges, so \(\psi_{a}=\exists v_{2}(v_{2}=\hat{x}_{1}\wedge\psi_{c}\wedge\psi_{d})\). Figure 1: An example graph \(H\) together with a tree decomposition for it, consisting of the tree \(T\) and the bag function \(B\) indicated using the small gray mapping arrows. A consistent numbering \(p\) is indicated in red. For the node \(b\) the situation is very similar, but there is now an edge \(\{3,5\}\) in \(H\). This means that we must check that the nodes \(v_{1}\), representing \(3\), and \(v_{2}\), representing \(5\), are connected in the input structure. This yields \(\psi_{b}=\exists v_{2}(v_{2}=\hat{x}_{5}\wedge Ev_{1}v_{2}\wedge\psi_{c})\). For the node \(c\), we only have one new node (2) with a new index \((3=p(2))\), but now there are two intra-bag edges in \(H\), namely \(\{1,2\}\in E(H)\) and \(\{2,3\}\in E(H)\). This yields: \(\psi_{c}=\exists v_{3}(v_{3}=\hat{x}_{2}\wedge Ev_{3}v_{1}\wedge Ev_{3}v_{2})\), where \(Ev_{1}v_{3}\) checks whether for \(\{2,3\}\in E(H)\) there is a corresponding edge in the input structure (recall that \(p(2)=3\) and \(p(3)=1\)) and \(Ev_{3}v_{2}\) checks the same for \(\{1,2\}\).