In both cases it can be verified that $L^{\prime}_{t_{p}}$ has the desired
properties.

The case of a tree-node $t_{p}$ that has two children $t$ and $t^{\prime}$ can
be handled in the same way: Let $A_{2}$ be constructed for $t$ as described
above, and let $A^{\prime}_{2}$ be constructed for $t^{\prime}$ in the
analogous way; the construction is completed by letting

$L^{\prime}_{t_{p}}\ \coloneqq\
(\;(L_{t_{p}}\mathbin{\cdot}A_{2})\,\mathbin{\cdot}A^{\prime}_{2}\,)\,.$

This completes the proof of part b of Theorem 7.12. ∎

See Appendix D.4 for an example illustrating the above construction. It helps
to get some insight into $k$-labeled incidence graphs and especially into
transitions.

###  D.3 Missing pieces in the proof of part b of Theorem 7.12

In case that ${X_{r}}=\varnothing$:

###### Proof that
${X_{b}}\subseteq\operatorname{dom}(b_{A_{1}})\setminus\operatorname{img}(g_{A_{1}})$.

It is clear that ${X_{b}}\subseteq\operatorname{dom}(b_{A_{1}})$ holds since
$c(t)=\operatorname{dom}(b_{L_{t}})=\operatorname{dom}(b_{L_{t}})$. Assume for
contradiction, that there exists an $i\in\operatorname{dom}(g_{A_{1}})$ such
that $g_{A_{1}}(i)=\ell\in{X_{b}}$. We have
$b_{A_{1}}(\ell)=b_{L_{t}^{\prime}}(\ell)$ and
$i\in\operatorname{dom}(r_{t})\cap\operatorname{dom}(r_{t_{p}})$, thus
$c(s(t,v_{i}))=\ell$. Since $\ell\in{X_{b}}$ we have $c(t,\ell)\neq
c(t_{p},\ell)$, which means $s(t,v_{i})\neq s(t_{p},v_{i})$. But this
contradicts our assumption that ${X_{r}}=\varnothing$. Therefore, such an $i$
cannot exist. ∎

###### Proof that $g_{t_{p}}$ and $g_{A_{2}}$ are compatible.

Assume for contradiction that there exists an
$i\in\operatorname{dom}(g_{t_{p}})\cap\operatorname{dom}(g_{A_{2}})$ such that
$g_{t_{p}}(i)\neq g_{A_{2}}(i)$. We have that $g_{A_{2}}(i)=g_{t}(i)$.
Therefore, $g_{t_{p}}(i)=c(s(t_{p},v_{i}))\neq c(s(t,v_{i}))=g_{t}(i)$. Then
$s(t_{p},v_{i})\neq s(t,v_{i})$ must hold, which contradicts
${X_{r}}=\varnothing$. ∎

In case that ${X_{r}}\neq\varnothing$:

###### Proof that $\operatorname{img}(f)\subseteq{X_{b}}$ and $f$ is a
transition for $g_{A_{1}}$.

Let $\ell$ be an element of $\operatorname{img}(f)$, and
$i\in(\operatorname{dom}(r_{t})\cap\operatorname{dom}(r_{t_{p}}))$ such that
$s(t,v_{i})\neq s(t_{p},v_{i})$ and $f(i)=g_{t_{p}}(i)=\ell$. Now, assume for
contradiction that $\ell\not\in{X_{b}}$, i.e. $c(t,\ell)=c(t_{p},\ell)$. This
would mean that $s(t,v_{i})=s(t_{p},v_{i})$, because $s$ is a schedule. This
clearly is a contradiction. ∎

###### Proof that
${\tilde{X}_{b}}\subseteq\operatorname{dom}(b_{\tilde{A}_{1}})\setminus\operatorname{img}(g_{\tilde{A}_{1}})$.

It is clear that
${\tilde{X}_{b}}\subseteq(\operatorname{dom}(b_{L_{t}^{\prime}})\setminus\hat{X}_{b})\subseteq\operatorname{dom}(b_{\tilde{A}_{1}})$.
Assume for contradiction, that there exists an
$i\in\operatorname{dom}(g_{\tilde{A}_{1}})$ such that
$g_{\tilde{A}_{1}}(i)=\ell\in{\tilde{X}_{b}}$. Since
$\ell\not\in\operatorname{img}(f)$ we have
$g_{\tilde{A}_{1}}(i)=g_{L_{t}^{\prime}}(i)=\ell$. Since
$\ell\in{\tilde{X}_{b}}\subseteq{X_{b}}$ we have $c(t,\ell)\neq
c(t_{p},\ell)$, which means $s(t,v_{i})\neq s(t_{p},v_{i})$. Therefore,
$i\in\operatorname{dom}(f)$ and $f(i)=\ell$, i.e.
$\ell\in\operatorname{img}(f)$. This contradicts our assumption that
$\ell\in{\tilde{X}_{b}}={X_{b}}\setminus\operatorname{img}(f)$. ∎

###### Proof that $g_{t_{p}}$ and $g_{A_{2}}$ are compatible.

Assume for contradiction that there exists an
$i\in\operatorname{dom}(g_{t_{p}})\cap\operatorname{dom}(g_{A_{2}})$ such that
$g_{t_{p}}(i)\neq g_{A_{2}}(i)$. If $i\in\operatorname{dom}(f)$, then
$f(i)=g_{t_{p}}(i)$ and since $f\subseteq g_{A_{2}}$ we have a contradiction.
Therefore, let $i\not\in\operatorname{dom}(f)$. Then we have that
$g_{A_{2}}(i)=g_{t}(i)$. Therefore, $g_{t_{p}}(i)=c(s(t_{p},v_{i}))\neq
c(s(t,v_{i}))=g_{t}(i)$. Then $s(t_{p},v_{i})\neq s(t,v_{i})$ must hold, which
contradicts $i\not\in\operatorname{dom}(f)$. ∎

###  D.4 An example illustrating the construction in the proof of part b of
Theorem 7.12

In this section we will define mappings “inline” like this: $f\coloneqq\\{a\to
b,u\to v,x\to y\\}$ means $\operatorname{dom}(f)=\\{a,u,x\\}$ and $f(a)=b$,
$f(u)=v$ and $f(x)=y$.

We will draw a lot of guarded $2$-labeled incidence graphs in this example. In
the same way as in the proof, the red vertex $v_{i}$ is either labeled with
$i$ or it is not labeled at all. Therefore, we colour $v_{i}$ red to indicate,
that $r(i)=v_{i}$ and black to indicate that $i\not\in\operatorname{dom}(r)$,
i.e. the label $i$ is not used. Since we only have two blue labels, we label a
blue vertex with
${\color[rgb]{0,0.45703125,0.51171875}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.45703125,0.51171875}1}$
or
${\color[rgb]{0,0.45703125,0.51171875}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.45703125,0.51171875}2}$
respectively to indicate, that the corresponding label is mapped to that
vertex. If a blue vertex has no label, we give it an alphabetical name – but
we colour it blue anyway to better distinguish it from red vertices.

Edges between blue and red vertices are indicated by a dotted line [inner
sep=0pt, baseline=(base)] (base) at (0,-.5ex) ; [edge] (0,0) – (0.5,0); .
Since all guarded $2$-labeled incidence graphs have real guards, a blue vertex
with label $j$ is only a guard of a red vertex $i$, if they are neighbours,
therefore we draw the edge dotted and thick [inner sep=0pt, baseline=(base)]
(base) at (0,-.5ex) ; [edge, guard] (0,0) – (0.5,0); to indicate that the blue
vertex is the red vertex’ guard.

[ every node/.style=regular, ] (S) at (4,0) $v_{1}$; (Z) at (-2,0) $v_{2}$;
(ZP) at (2,0) $v_{3}$;

(X) at (-1,1) $v_{4}$; (XP) at (1,1) $v_{5}$; (Y) at (-1,-1) $v_{6}$; (YP) at
(1,-1) $v_{7}$;

(C) at (-3,1) $v_{8}$; (CP) at (-3,-1) $v_{9}$; (F) at (3,1) $v_{10}$; (FP) at
(3,-1) $v_{11}$;

[blue] (a) at ($(X)!0.5!(XP)+(0pt,15pt)$) $a$; [dotted] (C) – (a) – (X);
[dotted] (XP) – (a) – (F); [dotted] (S) edge[bend right=45] (a);

[circle, blue] (b) at ($(Y)!0.5!(YP)+(0pt,-15pt)$) $b$; [dotted] (CP) – (b) –
(Y); [dotted] (YP) – (b) – (FP); [dotted] (S) edge[bend left=45] (b);

[blue] (c) at ($(C)!0.5!(CP)!0.3!(Z)$) $c$; [dotted] (C) – (c) – (Z); [dotted]
(CP) – (c);

[blue] (d) at ($(Z)!0.5!(X)$) $d$; [dotted] (Z) – (d) – (X);

[blue] (e) at ($(Z)!0.5!(Y)$) $e$; [dotted] (Z) – (e) – (Y);

[blue] (f) at ($(F)!0.5!(FP)!0.3!(ZP)$) $f$; [dotted] (F) – (f) – (ZP);
[dotted] (FP) – (f);

[blue] (g) at ($(ZP)!0.5!(XP)$) $g$; [dotted] (ZP) – (g) – (XP);

[blue] (h) at ($(ZP)!0.5!(YP)$) $h$; [dotted] (ZP) – (h) – (YP);

[blue] (m) at ($(X)!0.5!(Y)$) $m$; [dotted] (X) – (m) – (Y);

[blue] (n) at ($(XP)!0.5!(YP)$) $n$; [dotted] (XP) – (n) – (YP);

[blue] (j) at (0,0) $j$; (J) at ($(a)!0.5!(j)$) $v_{0}$; [dotted] (X) – (j) –
(XP); [dotted] (Y) – (j) – (YP); [dotted] (J) – (j);

Figure 1: An incidence graph ${I}$ (${I}$ is a modified version of
$\mathcal{Q}_{2}$ in [12]). Blue nodes are depicted in blue and named
$a,b,\ldots{}$, red nodes are depicted in black and named
$v_{1},v_{2},\ldots{}$, and edges are indicated by dotted lines. Figure 2: An
ehd $D$ of the incidence graph $I$ of Figure 1, witnessing that
$\operatorname{ehw}(I)\leqslant 2$. The names of the tree-nodes are
$t_{1},t_{2},\ldots{}$, the tree-node’s bag is the set of all the depicted
nodes $v_{i}$, and the tree-node’s cover consists of the nodes depicted
directly left to each symbol “$\\{$”.

We consider the particular incidence graph $I$ and ehd
$D=(T,\textit{bag},\textit{cover})$ depicted in the Figures 1 and 2, and we
let $k\coloneqq 2$. Note that $D$ has the properties provided by Lemma D.1.
Defining a $2$-colouring $c$ is easy: we colour each blue node of $I$ that is
depicted first in its tree-node with the number 1, and all other blue nodes
are coloured with the number 2 (e.g., $c(j)=c(m)=1$ and $c(b)=c(f)=2$). In
total, we get the following $2$-colouring $c$.

$e\in B({I})$ | $a$ | $b$ | $c$ | $d$ | $e$ | $f$ | $g$ | $h$ | $j$ | $m$ | $n$
---|---|---|---|---|---|---|---|---|---|---|---
$c(e)$ | $1$ | $2$ | $2$ | $1$ | $1$ | $2$ | $1$ | $1$ | $1$ | $1$ | $1$

Our schedule is easy to define as well, since in many cases, the
neighbourhoods of the blue vertices covering the bags do not intersect. For
example, we have no other choice but to set $s(t_{5},v_{2})=s(t_{5},v_{4})=d$
and $s(t_{3},v_{4})=m$, $s(t_{3},v_{9})=c$ and so on. The complete schedule
$s$ looks like this:

$s$ | $t_{1}$ | $t_{2}$ | $t_{3}$ | $t_{4}$ | $t_{5}$ | $t_{6}$ | $t_{7}$ | $t_{8}$
---|---|---|---|---|---|---|---|---
$v_{0}$ | $j$ | – | – | – | – | – | – | –
$v_{1}$ | $b$ | $b$ | – | – | – | – | – | –
$v_{2}$ | – | – | $c$ | – | $d$ | $e$ | – | –
$v_{3}$ | – | – | – | $f$ | – | – | $g$ | $h$
$v_{4}$ | $j$ | $a$ | $m$ | $d$ | – | – | – | –
$v_{5}$ | $j$ | $a$ | – | $n$ | – | – | $g$ | –
$v_{6}$ | $j$ | $b$ | $m$ | – | – | $e$ | – | –
$v_{7}$ | $j$ | $b$ | – | $n$ | – | – | – | $h$
$v_{8}$ | – | $a$ | $c$ | – | – | – | – | –
$v_{9}$ | $b$ | $b$ | $c$ | – | – | – | – | –
$v_{10}$ | – | $a$ | – | $f$ | – | – | – | –
$v_{11}$ | $b$ | $b$ | – | $f$ | – | – | – | –

Now, to construct ${I}$ we start at the bottom of $D$, so let us take a look
at the nodes $t_{5}$, $t_{6}$ and their parent $t_{3}$. Then, $L_{t_{3}}$,
$L_{t_{5}}$ and $L_{t_{6}}$ look like this:

$L_{t_{3}}$: |  $L_{t_{5}}$: |  $L_{t_{6}}$:
---|---|---
[ every node/.style=regular ] [red] (Z) at (-2,0) $v_{2}$; [red] (X) at (-1,1) $v_{4}$; [red] (Y) at (-1,-1) $v_{6}$; [red] (C) at (-3,1) $v_{8}$; [red] (CP) at (-3,-1) $v_{9}$; [blue] (c) at ($(C)!0.5!(CP)!0.3!(Z)$) $2$; [guard, edge] (C) – (c) – (Z); [guard, edge] (CP) – (c); [blue] (m) at ($(X)!0.5!(Y)$) $1$; [guard, edge] (X) – (m) – (Y); |  [ every node/.style=regular, ] [red] (Z) at (-2,0) $v_{2}$; [red] (X) at (-1,1) $v_{4}$; [blue] (d) at ($(Z)!0.5!(X)$) $1$; [edge, guard] (Z) – (d) – (X); |  [ every node/.style=regular, ] [red] (Z) at (-2,0) $v_{2}$; [red] (Y) at (-1,-1) $v_{6}$; [blue] (e) at ($(Z)!0.5!(Y)$) $1$; [edge, guard] (Z) – (e) – (Y);

We want to glue $L_{t_{5}}$ and $L_{t_{6}}$ with $L_{t_{3}}$, since $t_{3}$ is
the parent of $t_{5}$ and $t_{6}$. If we approach this in a naive way, we
would immediately fail, since we would merge the blue vertices with label $1$,
but the $1$-labeled vertex in e.g. $L_{t_{5}}$ should represent $d$, whereas
the one in $t_{3}$ should correspond to $m$. Hence, simply glueing these would
result in the wrong incidence graph.

Here come the transitions into play. We want to apply a transition $f_{5}$ to
$L_{t_{5}}$ and $f_{6}$ to $L_{t_{6}}$ respectively, so that we mitigate the
aforementioned issue. If we want to remove the label $1$ and insert a new one
with this label, we have to find new guards for $v_{4}$ and $v_{2}$. The
schedule $s$ helps us with this. It tells us, that $2$ is a suitable guard for
$v_{2}$ and $1$ is suitable for $v_{4}$ since $c(s(t_{3},v_{2}))=c(c)=2$ and
$c(s(t_{3},v_{4}))=c(m)=1$. We use the guards according to $t_{3}$, because
then we can be sure that we do not make the same mistake as outlined above
when glueing. Hence, we set $f_{5}\coloneqq\\{2\to 2,4\to 1\\}$. With the same
argument we get $f_{6}\coloneqq\\{2\to 2,6\to 1\\}$. Applying these
transitions gives us the following:

$A_{t_{5}}\coloneqq L_{t_{5}}[{\leadsto}f_{5}]$: |  $A_{t_{6}}\coloneqq L_{t_{6}}[{\leadsto}f_{6}]$:
---|---
[ every node/.style=regular ] [red] (Z) at (-2,0) $v_{2}$; [red] (X) at (-1,1) $v_{4}$; [blue] (c) at (-2.7,0) $2$; [edge, guard] (c) – (Z); [blue] (d) at ($(Z)!0.5!(X)$) $d$; [edge] (Z) – (d) – (X); [blue] (m) at (-1,0) $1$; [edge, guard] (X) – (m); |  [ every node/.style=regular, ] [red] (Z) at (-2,0) $v_{2}$; [red] (Y) at (-1,-1) $v_{6}$; [blue] (c) at (-2.7,0) $2$; [edge, guard] (c) – (Z); [blue] (e) at ($(Z)!0.5!(Y)$) $e$; [edge] (Z) – (e) – (Y); [blue] (m) at (-1,0) $1$; [edge, guard] (m) – (Y);

If we glue these with $L_{t_{3}}$, we see that nothing bad happens any more:

$L_{t_{3}}^{\prime}\coloneqq((L_{n_{3}}\mathbin{\cdot}A_{t_{5}})\mathbin{\cdot}A_{t_{6}})$:

[ every node/.style=circle, ] [red] (Z) at (-2,0) $v_{2}$;

[red] (X) at (-1,1) $v_{4}$; [red] (Y) at (-1,-1) $v_{6}$;

[red] (C) at (-3,1) $v_{8}$; [red] (CP) at (-3,-1) $v_{9}$; [blue] (c) at
($(C)!0.5!(CP)!0.3!(Z)$) $2$; [edge, guard] (C) – (c) – (Z); [edge, guard]
(CP) – (c);

[blue] (d) at ($(Z)!0.5!(X)$) $d$; [edge] (Z) – (d) – (X);

[blue] (e) at ($(Z)!0.5!(Y)$) $e$; [edge] (Z) – (e) – (Y);

[blue] (m) at ($(X)!0.5!(Y)$) $1$; [edge, guard] (X) – (m) – (Y);

We now have constructed a guarded $2$-labeled incidence graph
$L_{t_{3}}^{\prime}$, that is isomorphic to ${\hat{I}_{t_{3}}}$ – the subgraph
induced by $T_{t_{3}}$.

Next we apply the same procedure to the other branch of $D$, i.e. to $t_{7}$,
$t_{8}$ and their parent $t_{4}$:

$L_{t_{4}}$: |  $L_{t_{7}}$: |  $L_{t_{8}}$:
---|---|---
[ every node/.style=regular, ] [red] (ZP) at (2,0) $v_{3}$; [red] (XP) at (1,1) $v_{5}$; [red] (YP) at (1,-1) $v_{7}$; [red] (F) at (3,1) $v_{10}$; [red] (FP) at (3,-1) $v_{11}$; [blue] (f) at ($(F)!0.5!(FP)!0.3!(ZP)$) $2$; [edge, guard] (F) – (f) – (ZP); [edge, guard] (FP) – (f); [blue] (n) at ($(XP)!0.5!(YP)$) $1$; [edge, guard] (XP) – (n) – (YP); |  [ every node/.style=regular, ] [red] (ZP) at (2,0) $v_{3}$; [red] (XP) at (1,1) $v_{5}$; [blue] (g) at ($(ZP)!0.5!(XP)$) $1$; [edge, guard] (ZP) – (g) – (XP); |  [ every node/.style=circle, ] [red] (ZP) at (2,0) $v_{3}$; [red] (YP) at (1,-1) $v_{7}$; [blue] (h) at ($(ZP)!0.5!(YP)$) $1$; [edge, guard] (ZP) – (h) – (YP);

We set $f_{7}\coloneqq\\{3\to 2,5\to 1\\}$ and $f_{8}\coloneqq\\{3\to 2,7\to
1\\}$, applying these yields:

$A_{t_{7}}\coloneqq L_{t_{7}}[{\leadsto}f_{7}]$: |  $A_{t_{8}}\coloneqq L_{t_{8}}[{\leadsto}f_{8}]$:
---|---
[ every node/.style=regular, ] [red] (ZP) at (2,0) $v_{3}$; [red] (XP) at (1,1) $v_{5}$; [blue] (f) at (2.7,0) $2$; [edge, guard] (f) – (ZP); [blue] (g) at ($(ZP)!0.5!(XP)$) $g$; [edge] (ZP) – (g) – (XP); [blue] (n) at (1,0) $1$; [edge, guard] (XP) – (n); |  [ every node/.style=circle, ] [red] (ZP) at (2,0) $v_{3}$; [red] (YP) at (1,-1) $v_{7}$; [blue] (f) at (2.7,0) $2$; [edge, guard] (f) – (ZP); [blue] (h) at ($(ZP)!0.5!(YP)$) $h$; [edge] (ZP) – (h) – (YP); [blue] (n) at (1,0) $1$; [edge, guard] (n) – (YP);

And then glueing gives us again a guarded $2$-labeled incidence graph
$L_{t_{4}}^{\prime}$ isomorphic to the subgraph ${\hat{I}_{t_{4}}}$ induced by
$T_{t_{4}}$.

$L_{t_{4}}^{\prime}\coloneqq((L_{t_{4}}\mathbin{\cdot}A_{t_{7}})\mathbin{\cdot}A_{t_{8}})$:

[ every node/.style=regular, ] [red] (ZP) at (2,0) $v_{3}$;

[red] (XP) at (1,1) $v_{5}$; [red] (YP) at (1,-1) $v_{7}$;

[red] (F) at (3,1) $v_{10}$; [red] (FP) at (3,-1) $v_{11}$;

[blue] (f) at ($(F)!0.5!(FP)!0.3!(ZP)$) $2$; [edge, guard] (F) – (f) – (ZP);
[edge, guard] (FP) – (f);

[blue] (g) at ($(ZP)!0.5!(XP)$) $g$; [edge] (ZP) – (g) – (XP);

[blue] (h) at ($(ZP)!0.5!(YP)$) $h$; [edge] (ZP) – (h) – (YP);

[blue] (n) at ($(XP)!0.5!(YP)$) $1$; [edge, guard] (XP) – (n) – (YP);

In the next step we want to handle $t_{3}$, $t_{4}$ and their parent $t_{2}$.
Obviously, this time we do not glue $L_{t_{3}}$, $L_{t_{4}}$ with $L_{t_{2}}$.
Instead, we glue the incidence graphs we just constructed, that is
$L_{t_{3}}^{\prime}$ and $L_{t_{4}}^{\prime}$.

Again, we first have to apply transitions to make them compatible to
$L_{t_{2}}$. For $t_{3}$, we want $v_{4}$, $v_{8}$ to be guarded by a new
vertex labeled $1$ and $v_{6},v_{9}$ by one labeled $2$. So we set
$f_{3}\coloneqq\\{4\to 1,6\to 2,8\to 1,9\to 2\\}$ and analogously
$f_{4}\coloneqq\\{5\to 1,7\to 2,10\to 1,11\to 2\\}$. But, what do we do with
$v_{2}$ and $v_{3}$? Since they no longer appear in the bag of $t_{2}$, we
know that they will no longer appear in the construction _at all_ because of
the connectedness of vertices, so there is no need to transition them to new
guards. But, because we do not include them, $f_{3}$ is not a transition for
$L_{t_{3}}^{\prime}$ (and $f_{4}$ not for $L_{t_{4}}^{\prime}$), since
$g_{L_{t_{3}}}(2)=2\in\operatorname{img}(f_{3})$ but
$2\not\in\operatorname{dom}(f_{3})$, thus violating the requirements of a
transition. Analogously $g_{t_{4}}(3)=2\in\operatorname{img}(f_{4})$, but
$3\not\in\operatorname{dom}(f_{4})$. But, as we have seen a moment ago, we can
easily remedy this situation for $L_{t_{3}}^{\prime}$ by removing the label
$2$ from the red vertex $v_{2}$, by setting $X_{r,t_{3}}\coloneqq\\{2\\}$.

$A_{t_{3}}\coloneqq
L_{t_{3}}^{\prime}[X_{r,t_{3}}{\to}\bullet][{\leadsto}f_{3}]$:

[ every node/.style=regular, ] (Z) at (-2,0) $v_{2}$;

[red] (X) at (-1,1) $v_{4}$; (XP) at (1,1) ; [red] (Y) at (-1,-1) $v_{6}$;
(YP) at (1,-1) ;

[red] (C) at (-3,1) $v_{8}$; [red] (CP) at (-3,-1) $v_{9}$;

[blue] (a) at ($(X)!0.5!(XP)+(0pt,15pt)$) $1$; [edge, guard] (C) – (a) – (X);

[blue] (b) at ($(Y)!0.5!(YP)+(0pt,-15pt)$) $2$; [edge, guard] (CP) – (b) –
(Y);

[blue] (c) at ($(C)!0.5!(CP)!0.3!(Z)$) $c$; [edge] (C) – (c) – (Z); [edge]
(CP) – (c);

[blue] (d) at ($(Z)!0.5!(X)$) $d$; [edge] (Z) – (d) – (X);

[blue] (e) at ($(Z)!0.5!(Y)$) $e$; [edge] (Z) – (e) – (Y);

[blue] (m) at ($(X)!0.5!(Y)$) $m$; [edge] (X) – (m) – (Y);

In the same way, removing the label $3$ from $v_{3}$ in $L_{t_{4}}^{\prime}$
fixes our violation of the requirements, turning $f_{4}$ into a proper
transition. I.e. we set $X_{r,t_{4}}\coloneqq\\{3\\}$.

$A_{t_{4}}\coloneqq
L_{t_{4}}^{\prime}[X_{r,t_{4}}{\to}\bullet][{\leadsto}f_{4}]$:

[ every node/.style=regular, ] (ZP) at (2,0) $v_{3}$;

(X) at (-1,1) ; [red] (XP) at (1,1) $v_{5}$; (Y) at (-1,-1) ; [red] (YP) at
(1,-1) $v_{7}$;

[red] (F) at (3,1) $v_{10}$; [red] (FP) at (3,-1) $v_{11}$;

[blue] (a) at ($(X)!0.5!(XP)+(0pt,15pt)$) $1$; [guard, edge] (XP) – (a) – (F);

[blue] (b) at ($(Y)!0.5!(YP)+(0pt,-15pt)$) $2$; [guard, edge] (YP) – (b) –
(FP);

[blue] (f) at ($(F)!0.5!(FP)!0.3!(ZP)$) $f$; [edge] (F) – (f) – (ZP); [edge]
(FP) – (f);

[blue] (g) at ($(ZP)!0.5!(XP)$) $g$; [edge] (ZP) – (g) – (XP);

[blue] (h) at ($(ZP)!0.5!(YP)$) $h$; [edge] (ZP) – (h) – (YP);

[blue] (n) at ($(XP)!0.5!(YP)$) $n$; [edge] (XP) – (n) – (YP);

Glueing these with $L_{t_{2}}$ gives us the following:

$L_{t_{2}}^{\prime}\coloneqq((L_{t_{2}}\mathbin{\cdot}A_{t_{3}})\mathbin{\cdot}A_{t_{4}})$:

[ every node/.style=regular, ] [red] (S) at (4,0) $v_{1}$; (Z) at (-2,0)
$v_{2}$; (ZP) at (2,0) $v_{3}$;

[red] (X) at (-1,1) $v_{4}$; [red] (XP) at (1,1) $v_{5}$; [red] (Y) at (-1,-1)
$v_{6}$; [red] (YP) at (1,-1) $v_{7}$;

[red] (C) at (-3,1) $v_{8}$; [red] (CP) at (-3,-1) $v_{9}$; [red] (F) at (3,1)
$v_{10}$; [red] (FP) at (3,-1) $v_{11}$;

[blue] (a) at ($(X)!0.5!(XP)+(0pt,15pt)$) $1$; [guard, edge] (C) – (a) – (X);
[guard, edge] (XP) – (a) – (F); [edge] (S) edge[bend right=45] (a);

[blue] (b) at ($(Y)!0.5!(YP)+(0pt,-15pt)$) $2$; [guard, edge] (CP) – (b) –
(Y); [guard, edge] (YP) – (b) – (FP); [edge, guard] (S) edge[bend left=45]
(b);

[blue] (c) at ($(C)!0.5!(CP)!0.3!(Z)$) $c$; [edge] (C) – (c) – (Z); [edge]
(CP) – (c);

[blue] (d) at ($(Z)!0.5!(X)$) $d$; [edge] (Z) – (d) – (X);

[blue] (e) at ($(Z)!0.5!(Y)$) $e$; [edge] (Z) – (e) – (Y);

[blue] (f) at ($(F)!0.5!(FP)!0.3!(ZP)$) $f$; [edge] (F) – (f) – (ZP); [edge]
(FP) – (f);

[blue] (g) at ($(ZP)!0.5!(XP)$) $g$; [edge] (ZP) – (g) – (XP);

[blue] (h) at ($(ZP)!0.5!(YP)$) $h$; [edge] (ZP) – (h) – (YP);

[blue] (m) at ($(X)!0.5!(Y)$) $m$; [edge] (X) – (m) – (Y);

[blue] (n) at ($(XP)!0.5!(YP)$) $n$; [edge] (XP) – (n) – (YP);

Now we have to repeat this procedure one last time. We want
$v_{4},v_{5},v_{6}$ and $v_{7}$ to be guarded by a new vertex labeled $1$. For
that, we remove the labels from $v_{8}$ and $v_{10}$. Thus, we define
$f_{2}\coloneqq\\{4\to 1,5\to 1,6\to 1,7\to 1\\}$ and
$X_{r,t_{2}}\coloneqq\\{8,10\\}$. Glueing the resulting $2$-guarded incidence
graph
$A_{t_{2}}\coloneqq(L_{t_{2}}^{\prime}[X_{r,t_{2}}{\to}\bullet])[{\leadsto}f_{2}]$
with $L_{t_{1}}$ we get:

$L_{t_{1}}^{\prime}\coloneqq(L_{t_{1}}\mathbin{\cdot}A_{t_{2}})$:

[ every node/.style=regular, ] [red] (S) at (4,0) $v_{1}$; (Z) at (-2,0)
$v_{2}$; (ZP) at (2,0) $v_{3}$;

[red] (X) at (-1,1) $v_{4}$; [red] (XP) at (1,1) $v_{5}$; [red] (Y) at (-1,-1)
$v_{6}$; [red] (YP) at (1,-1) $v_{7}$;

(C) at (-3,1) $v_{8}$; [red] (CP) at (-3,-1) $v_{9}$; (F) at (3,1) $v_{10}$;
[red] (FP) at (3,-1) $v_{11}$;

[blue] (a) at ($(X)!0.5!(XP)+(0pt,15pt)$) $a$; [edge] (C) – (a) – (X); [edge]
(XP) – (a) – (F); [edge] (S) edge[bend right=45] (a);

[blue] (b) at ($(Y)!0.5!(YP)+(0pt,-15pt)$) $2$; [edge, guard] (CP) – (b) –
(FP); [edge, guard] (S) edge[bend left=45] (b); [edge] (YP) – (b) – (Y);

[blue] (c) at ($(C)!0.5!(CP)!0.3!(Z)$) $c$; [edge] (C) – (c) – (Z); [edge]
(CP) – (c);

[blue] (d) at ($(Z)!0.5!(X)$) $d$; [edge] (Z) – (d) – (X);

[blue] (e) at ($(Z)!0.5!(Y)$) $e$; [edge] (Z) – (e) – (Y);

[blue] (f) at ($(F)!0.5!(FP)!0.3!(ZP)$) $f$; [edge] (F) – (f) – (ZP); [edge]
(FP) – (f);

[blue] (g) at ($(ZP)!0.5!(XP)$) $g$; [edge] (ZP) – (g) – (XP);

[blue] (h) at ($(ZP)!0.5!(YP)$) $h$; [edge] (ZP) – (h) – (YP);

[blue] (m) at ($(X)!0.5!(Y)$) $m$; [edge] (X) – (m) – (Y);

[blue] (n) at ($(XP)!0.5!(YP)$) $n$; [edge] (XP) – (n) – (YP);

[blue] (j) at (0,0) $1$; [red] (J) at ($(a)!0.5!(j)$) $v_{0}$; [guard, edge]
(X) – (j) – (XP); [guard, edge] (Y) – (j) – (YP); [guard, edge] (J) – (j);

Which is obviously isomorphic to the incidence graph ${I}_{E}$ depicted in
Figure 1.

Note that we did not remove blue labels in this construction, which is
possible (and necessary) by the definition of $k$-labeled incidence graphs. We
need to do this in cases where we do not have labeled red vertices in the bags
connecting the blue ones, so that we can apply a transition. Imagine for
example the case that neighbouring bags are disjoint. We can handle this by
removing all red labels and then all blue labels from one of these incidence
graphs. On the other hand, we do need transitions, as we can easily verify
that we can not construct the incidence graph ${I}_{E}$ by removing blue
labels instead of applying transitions, without “temporarily leaving labeled
red vertices unguarded”, which must be prohibited. Because if we were to allow
this, then it would be easy to construct $k$-guarded incidence graphs with
entangled hypertree width larger than $k$.

###  D.5 Proof of Lemma 7.15

We first prove the lemma on “ordinary” $k$-labeled incidence graphs.

  1. wide

Let $L$, $L_{1}$, $L_{2}$ be $k$-labeled incidence graphs. It holds that
$\operatorname{hom}((L_{1}\mathbin{\cdot}L_{2}),L)=\operatorname{hom}(L_{1},L)\cdot\operatorname{hom}(L_{2},L)$.

###### Proof.

We provide a bijection $f$ from
$\operatorname{Hom}((L_{1}\mathbin{\cdot}L_{2}),L)$ to
$\operatorname{Hom}(L_{1},L)\times\operatorname{Hom}(L_{2},L)$.
For $(h_{R},h_{B})\in\operatorname{Hom}((L_{1}\mathbin{\cdot}L_{2}),L)$ we
define

$f((h_{R},h_{B}))\coloneqq((h_{1,R},h_{1,B}),(h_{2,R},h_{2,B}))$

where

$h_{i,R}(v)=h_{R}(\pi_{i,R}(v))\;\text{ and }\;h_{i,B}(e)=h_{B}(\pi_{i,B}(e))$

for every $i\in[2]$ and all $v\in R(I_{L_{i}})$ and all $e\in B(I_{L_{i}})$.
We have to prove that

     * •

$f$ is well-defined, i.e. $(h_{1,R},h_{1,B})$ and $(h_{2,R},h_{2,B})$ are
homomorphisms;

     * •

$f$ is injective;

     * •

and $f$ is surjective.

We prove that $(h_{1,R},h_{1,B})$ is a homomorphism. In an analogous way, one
can prove that $(h_{2,R},h_{2,B})$ is homomorphism as well.

Let $(e,v)\in E(I_{L_{1}})$. We must show that this edge exists in the image
as well, i.e. $(h_{1,B}(e),\allowbreak h_{1,R}(v))\in E(I_{L})$. We have
$h_{1,R}(v)=h_{R}(\pi_{1,R}(v))=h_{R}([(v,1)]_{\sim_{R}})$ and
$h_{1,B}(e)=h_{B}(\pi_{1,B}(e))=h_{B}([(e,1)]_{\sim_{B}})$. By definition, we
have $([(e,1)]_{\sim_{B}},[(v,1)]_{\sim_{R}})\in
E(I_{(L_{1}\mathbin{\cdot}L_{2})})$, therefore
$(h_{B}([(e,1)]_{\sim_{B}}),h_{R}([(v,1)]_{\sim_{R}}))\in E(I_{L})$, since
$(h_{R},h_{B})$ is a homomorphism.

Let $i\in\operatorname{dom}(r_{L_{1}})$ and
$j\in\operatorname{dom}(b_{L_{1}})$. We must show, that
$h_{1,R}(r_{L_{1}}(i))=r_{L}(i)$ and $h_{1,B}(b_{L_{1}}(j))=b_{L}(j)$. This is
easy as well, since

$\displaystyle h_{1,R}(r_{L_{1}}(i))$
$\displaystyle=h_{R}(\pi_{1,R}(r_{L_{1}}(i)))$
$\displaystyle=h_{R}([(1,r_{L_{1}(i)})]_{\sim_{R}})$
$\displaystyle=h_{R}(r_{(L_{1}\mathbin{\cdot}L_{2})}(i))=r_{L}(i)\;,$

and

$\displaystyle h_{1,B}(b_{L_{1}}(j))$
$\displaystyle=h_{B}(\pi_{1,B}(b_{L_{1}}(j)))$
$\displaystyle=h_{B}([(1,b_{L_{1}(j)})]_{\sim_{B}})$
$\displaystyle=h_{B}(b_{(L_{1}\mathbin{\cdot}L_{2})}(j))=b_{L}(j)\;.$

Thus, $(h_{1,R},h_{1,B})$ and therefore, $f$ is well-defined.

It is easy to see, that $f$ is injective: Assume that there exists a
homomorphism
$(h_{R}^{\prime},h_{B}^{\prime})\in\operatorname{Hom}((L_{1}\mathbin{\cdot}L_{2}),L)$
such that $f(h_{R}^{\prime},h_{B}^{\prime})=f(h_{R},h_{B})$. Then we have for
every $i\in[2]$ that
$h_{R}([(v,i)]_{\sim_{R}})=h_{R}^{\prime}([(v,i)]_{\sim_{R}})$ holds for all
$v\in R(I_{L_{i}})$ and
$h_{B}([(e,i)]_{\sim_{B}})=h_{B}^{\prime}([(e,i)]_{\sim_{B}})$ holds for all
$e\in B(I_{L_{i}})$. Since these make up all vertices,
$(h_{R}^{\prime},h_{B}^{\prime})$ and $(h_{R},h_{B})$ agree on all values,
therefore they are equal.

Consider $(h_{1,R},h_{1,B})\in\operatorname{Hom}(L_{1},L)$ and
$(h_{2,R},h_{2,B})\in\operatorname{Hom}(L_{2},L)$. For every $i\in[2]$ let
$h_{R}([(v,i)]_{\sim_{R}})=h_{i,R}(v)$ for all $v\in R(I_{L_{i}})$ and
$h_{B}([(e,i)]_{\sim_{B}})=h_{i,B}(e)$ for all $e\in B(I_{L_{i}})$. Assume
that $h_{R}$ is ill-defined. Then there must be $v_{1}\in R(I_{L_{1}})$ and
$v_{2}\in R(I_{L_{2}})$ such that $v_{1}\in[(v_{2},2)]_{\sim_{R}}$ and
$h_{1,R}(v_{1})\neq h_{2,R}(v_{2})$. $v_{1}\in[(v_{2},2)]_{\sim_{R}}$ means
that there exists a
$j\in\operatorname{dom}(r_{L_{1}})\cap\operatorname{dom}(r_{L_{2}})$ such that
$r_{L_{1}}(j)=v_{1}$ and $r_{L_{2}}(j)=v_{2}$. But this means
$h_{1,R}(v_{1})=r_{L}(j)=h_{2,R}(v_{2})$, which is a contradiction. Thus,
$h_{R}$ is well-defined. The same argument works for $h_{B}$. With similar
arguments as we have used so far, it is easy to verify that
$(h_{R},h_{B})\in\operatorname{Hom}((L_{1}\mathbin{\cdot}L_{2}),L)$.

We showed that $f$ is well-defined, injective and surjective, thus bijective.
Therefore,
$|\operatorname{Hom}((L_{1}\mathbin{\cdot}L_{2}),L)|=|\operatorname{Hom}(L_{1},L)|\cdot|\operatorname{Hom}(L_{2},L)|$.
∎

  2. wiide

Let $L$, $L^{\prime}$ be $k$-labeled incidence graphs and let
${X_{r}}\coloneqq\\{i_{1},\dots,i_{\ell}\\}\subseteq\operatorname{dom}(r_{L})$
with $i_{1}<\cdots<i_{\ell}$. It holds that

$\operatorname{hom}(L[{X_{r}}{\to}\bullet],L^{\prime})=\sum_{\overline{v}\in
R(I_{L^{\prime}})^{\ell}}\operatorname{hom}(L,L^{\prime}[{X_{r}}{\to}\overline{v}])\;.$

###### Proof.

Let $(h_{R},h_{B})\in\operatorname{Hom}(L[{X_{r}}{\to}\bullet],L^{\prime})$ be
a homomorphism. Recall that $I_{L}=I_{L[{X_{r}}{\to}\bullet]}$, therefore we
can define the following tuple of red vertices in $L^{\prime}$:

$\overline{v}=(v_{i_{1}},\dots,v_{i_{\ell}})\coloneqq(h_{R}(r_{L}(i_{1})),\dots,h_{R}(r_{L}(i_{\ell})))\;.$

Clearly,
$(h_{R},h_{B})\in\operatorname{Hom}(L,L^{\prime}[{X_{r}}{\to}\overline{v}])$,
since it is a homomorphism from $I_{L}=I_{L[{X_{r}}{\to}\bullet]}$ to
$I_{L^{\prime}[{X_{r}}{\to}\overline{v}]}=I_{L^{\prime}}$, and we moved the
red labels onto $(v_{i_{1}},\dots,v_{i_{\ell}})$.

For any tuple $\overline{v}\in R(I_{L^{\prime}})^{\ell}$ it is easy to see
that

$\operatorname{Hom}(L,L^{\prime}[{X_{r}}{\to}\overline{v}])\ \subseteq\
\operatorname{Hom}(L[{X_{r}}{\to}\bullet],L^{\prime})\;.$

It is also easy to see, that for all $\overline{v}\neq\overline{v}^{\prime}\in
R(I_{L^{\prime}})^{\ell}$

$\operatorname{Hom}(L,L^{\prime}[{X_{r}}{\to}\overline{v}])\ \cap\
\operatorname{Hom}(L,L^{\prime}[{X_{r}}{\to}\overline{v}^{\prime}])\ =\
\varnothing\;.$

This finishes our proof. ∎

  3. wiiide

Let $L$, $L^{\prime}$ be $k$-labeled incidence graphs and let
${X_{b}}\subseteq\operatorname{dom}(b_{L})$ and $\ell\coloneqq|{X_{b}}|$. It
holds that

$\operatorname{hom}(L\langle{X_{b}}{\to}\bullet\rangle,L^{\prime})=\sum_{\overline{e}\in
B(I_{L^{\prime}})^{\ell}}\operatorname{hom}(L,L^{\prime}\langle{X_{b}}{\to}\overline{e}\rangle)\;.$

###### Proof.

The same argument as in the previous case works for this claim as well. ∎

  4. wivde

Let $L$, $L^{\prime}$ be $k$-labeled incidence graphs and let $f$ be a
transition for $L$. Let
${X_{b}}\coloneqq\operatorname{dom}(b_{L})\cap\operatorname{img}(f)\cap\operatorname{img}(g)$.
It holds that $\operatorname{hom}(L[{\leadsto}f],L^{\prime})=$

$\operatorname{hom}(M_{f},L^{\prime})\ \cdot\\!\\!\\!\sum_{\overline{e}\in
B(I_{L^{\prime}})^{\ell}}\\!\\!\\!\operatorname{hom}(L,L^{\prime}\langle{X_{b}}{\to}\overline{e}\rangle)\;.$

###### Proof.

This follows directly from 1) and 3) and Definition 7.8 (applying a
transition). ∎

Generalising these results to quantum $k$-labeled incidence graphs is
straightforward using simple linear arguments:

  1. 1.

$\operatorname{hom}((Q_{1}\mathbin{\cdot}Q_{2}),L)=$

$\displaystyle\sum_{i\in[d]\atop
j\in[d^{\prime}]}(\alpha_{i}\cdot\alpha_{j}^{\prime})\operatorname{hom}((L_{i}\mathbin{\cdot}L_{j}^{\prime}),L)$
$\displaystyle=$ $\displaystyle\sum_{i\in[d]\atop
j\in[d^{\prime}]}(\alpha_{i}\cdot\alpha_{j}^{\prime})\cdot\operatorname{hom}(L_{i},L)\cdot\operatorname{hom}(L^{\prime}_{j},L)$
$\displaystyle=$
$\displaystyle\sum_{i\in[d]}\Big{(}\alpha_{i}\operatorname{hom}(L_{i},L)\cdot\sum_{j\in[d^{\prime}]}\alpha_{j}^{\prime}\operatorname{hom}(L_{j}^{\prime},L)\Big{)}$
$\displaystyle=$
$\displaystyle\sum_{i\in[d]}\Big{(}\alpha_{i}\operatorname{hom}(L_{i},L)\cdot\operatorname{hom}(Q_{2},L)\Big{)}$
$\displaystyle=$
$\displaystyle\operatorname{hom}(Q_{2},L)\cdot\sum_{i\in[d]}\alpha_{i}\operatorname{hom}(L_{i},L)$
$\displaystyle=$
$\displaystyle\operatorname{hom}(Q_{2},L)\cdot\operatorname{hom}(Q_{1},L)$

  2. 2.

$\operatorname{hom}(Q[{X_{r}}{\to}\bullet],L)=$

$\displaystyle\sum_{i\in[d]}\alpha_{i}\operatorname{hom}(L_{i}[L{\to}\bullet],L)$
$\displaystyle=$
$\displaystyle\sum_{i\in[d]}\alpha_{i}\;\Big{(}\\!\\!\\!\\!\\!\sum_{\overline{v}\in
R(I_{L})^{\ell}}\\!\\!\\!\\!\operatorname{hom}(L_{i},L[{X_{r}}{\to}\overline{v}])\Big{)}$
$\displaystyle=$ $\displaystyle\\!\\!\\!\\!\\!\sum_{\overline{v}\in
R(I_{L})^{\ell}}\
\Big{(}\sum_{i\in[d]}\alpha_{i}\operatorname{hom}(L_{i},L[{X_{r}}{\to}\overline{v}])\Big{)}$
$\displaystyle=$ $\displaystyle\\!\\!\\!\\!\\!\sum_{\overline{v}\in
R(I_{L})^{\ell}}\ \operatorname{hom}(Q,L[{X_{r}}{\to}\overline{v}])$

  3. 3.

The same argument as in the previous case works for this claim as well.

  4. 4.

This follows directly from 1) and 3).∎Lemma 7.15

##  Appendix E Details ommitted in Section 8

###  E.1 Complete proof of Lemma 8.1

###### Proof of Lemma 8.1.

We proceed by induction based on Definition 7.10.

Base case:

1) $R(I)=\operatorname{img}(r)$, $B(I)=\operatorname{img}(b)$, and $L$ has
real guards. Obviously, $\operatorname{hom}(L,L^{\prime})\in\\{0,1\\}$. Let

$\displaystyle S_{E}$ $\displaystyle\coloneqq$
$\displaystyle\\{(j,i)\in\operatorname{dom}(b)\times\operatorname{dom}(r):(b(j),r(i))\in
E(I)\\},$ $\displaystyle S_{R}$ $\displaystyle\coloneqq$
$\displaystyle\\{(i,i^{\prime}):i,i^{\prime}\in\operatorname{dom}(r),\
i<i^{\prime},\ r(i)=r(i^{\prime})\\}\,,$ $\displaystyle S_{B}$
$\displaystyle\coloneqq$
$\displaystyle\\{(j,j^{\prime}):j,j^{\prime}\in\operatorname{dom}(b),\
j<j^{\prime},\ b(j)=b(j^{\prime})\\}\,.$

We choose $\varphi_{L,1}\coloneqq$

$\bigwedge_{(j,i)\in S_{E}}\\!\\!\\!E(\texttt{{e}}_{j},\texttt{{v}}_{i})\ \
\wedge\bigwedge_{(i,i^{\prime})\in
S_{R}}\\!\\!\\!\texttt{{v}}_{i}{=}\texttt{{v}}_{i^{\prime}}\ \
\wedge\bigwedge_{(j,j^{\prime})\in
S_{B}}\\!\\!\\!\texttt{{e}}_{j}{=}\texttt{{e}}_{j^{\prime}}\,.$

It is straightforward to verify that
$(\Delta_{g}\wedge\varphi_{L,1})\in\textsf{{GC}}^{{k}}$.

Let $L^{\prime}$ satisfy the lemma’s assumptions. Since $L^{\prime}$ has real
guards w.r.t. $g$ we have $\mathcal{I}_{L^{\prime}}\models\Delta_{g}$. By
construction of the formula $\varphi_{L,1}$ there is a homomorphism from $L$
to $L^{\prime}$ if, and only if,
$\mathcal{I}_{L^{\prime}}\models\varphi_{L,1}$. Thus, we are done for the case
$m=1$.
For $m=0$ we are done by choosing $\varphi_{L,0}\coloneqq\neg\,\varphi_{L,1}$.
For $m\geqslant 2$ we know that $\operatorname{hom}(L,L^{\prime})\neq m$.
Thus, we are done by choosing an arbitrary unsatisfiable formula; to be
specific we choose
$\varphi_{L^{\prime},m}\coloneqq(\varphi_{L^{\prime},0}\wedge\varphi_{L^{\prime},1})$.

Inductive step: We assume that the lemma’s statement is already shown for
$L=(I,r,b,g)\in\textsl{GLI}_{k}$ and for
$L_{i}=(I_{i},r_{i},b_{i},g_{i})\in\textsl{GLI}_{k}$ for $i\in[2]$ where
$g_{1},g_{2}$ are compatible. Our goal is to prove the lemma’s statement for
the particular
$\tilde{L}=(\tilde{I},\tilde{r},\tilde{b},\tilde{g})\in\textsl{GLI}_{k}$
considered in the following case distinction.

2) Let $\tilde{L}\coloneqq L[{X_{r}}{\to}\bullet]$ for some
${X_{r}}\subseteq\operatorname{dom}(r)$. If ${X_{r}}=\varnothing$ we are done
since $\tilde{L}=L$. If ${X_{r}}\neq\varnothing$ let $\ell\coloneqq|{X_{r}}|$
and let ${X_{r}}=\\{i_{1},\ldots,i_{\ell}\\}$ with $i_{1}<\cdots<i_{\ell}$.
Note that $\tilde{r}=r-{X_{r}}$, $\tilde{b}=b$, and $\tilde{g}=g-{X_{r}}$. We
let

$\varphi_{\tilde{L},0}\ \ \coloneqq\ \
\forall(\texttt{{v}}_{i_{1}},\dots,\texttt{{v}}_{i_{\ell}}).(\Delta_{g}\to\varphi_{L,0})\,.$

It is straightforward to verify that
$(\Delta_{\tilde{g}}\wedge\varphi_{\tilde{L},0})\in\textsf{{GC}}^{{k}}$.
For every $m\geqslant 1$ we let

$\varphi_{\tilde{L},m}\ \ \coloneqq\ \
\bigvee_{(\overline{c},\overline{m})\in\textit{Seg}(m)}\varphi_{\overline{c},\overline{m}}$

where for every
$(\overline{c},\overline{m})=((c_{1},\ldots,c_{d}),(m_{1},\ldots,m_{d}))\in\textit{Seg}(m)$
and $c\coloneqq\sum_{i\in[d]}c_{i}$ we let

$\begin{array}[]{ll}\varphi_{\overline{c},\overline{m}}\ \
\coloneqq&\exists^{\scalebox{0.6}{$=$}c}(\texttt{{v}}_{i_{1}},\dots,\texttt{{v}}_{i_{\ell}}).(\Delta_{g}\land\lnot\varphi_{L,0})\
\ \land\\\\[4.30554pt]
&\bigwedge_{j\in[d]}\left(\exists^{\scalebox{0.6}{$=$}c_{j}}(\texttt{{v}}_{i_{1}},\dots,\texttt{{v}}_{i_{\ell}}).(\Delta_{g}\land\varphi_{L,m_{j}}\right)\,.\end{array}$

It is straightforward to verify that
$(\Delta_{\tilde{g}}\wedge\varphi_{\overline{c},\overline{m}})\in\textsf{{GC}}^{{k}}$;
and hence also
$(\Delta_{\tilde{g}}\wedge\varphi_{\tilde{L},m})\in\textsf{{GC}}^{{k}}$.

Let $L^{\prime}=(I^{\prime},r^{\prime},b^{\prime},g^{\prime})$ satisfy the
lemma’s assumptions for $\tilde{L}$ instead of $L$. I.e., we have
$\operatorname{dom}(b^{\prime})\supseteq\operatorname{dom}(\tilde{b})=\operatorname{dom}(b)$,
$\operatorname{dom}(r^{\prime})\supseteq\operatorname{dom}(\tilde{r})=\operatorname{dom}(r)\setminus{X_{r}}$,
and $L^{\prime}$ has real guards w.r.t. $\tilde{g}$. Thus,
$\mathcal{I}_{L^{\prime}}\models\Delta_{\tilde{g}}$.
From Lemma 7.15 we know that

$n\ \coloneqq\ \operatorname{hom}(\tilde{L},L^{\prime})\ \ =\sum_{\bar{v}\in
R(I^{\prime})^{\ell}}\operatorname{hom}(L,L^{\prime}[{X_{r}}{\to}\overline{v}]).$
(9)

Note that $n=0$ $\iff$
$\operatorname{hom}(L,L^{\prime}[{X_{r}}{\to}\overline{v}])=0$ for all
$\bar{v}\in R(I^{\prime})^{\ell}$ $\iff$ for all $\bar{v}\in
R(I^{\prime})^{\ell}$ we have either
$\mathcal{I}_{L^{\prime}[{X_{r}}{\to}\overline{v}]}\not\models\Delta_{g}$
(this is in case that $\mathcal{I}_{L^{\prime}[{X_{r}}{\to}\overline{v}]}$
does not have real guards w.r.t. $g$) or
$\mathcal{I}_{L^{\prime}[{X_{r}}{\to}\overline{v}]}\models(\Delta_{g}\wedge\varphi_{L,0})$
$\iff$ $\mathcal{I}_{L^{\prime}}\models\varphi_{\tilde{L},0}$. Thus, the
formula $\varphi_{\tilde{L},0}$ has the desired meaning.

Let us now consider the case where $n\geqslant 1$. For every number
$m^{\prime}\in[n]$ let $S_{m^{\prime}}$ be the set of all $\bar{v}\in
R(I^{\prime})^{\ell}$ such that
$m^{\prime}=\operatorname{hom}(L,L^{\prime}[{X_{r}}{\to}\overline{v}])$. Let
$d^{\prime}$ be the number of distinct $m^{\prime}\in[n]$ for which
$S_{m^{\prime}}\neq\varnothing$, and let
$m^{\prime}_{1}<\cdots<m^{\prime}_{d^{\prime}}$ be an ordered list of all
$m^{\prime}\in[n]$ with $S_{m^{\prime}}\neq\varnothing$. For each
$j\in[d^{\prime}]$ let $c^{\prime}_{j}\coloneqq|S_{m^{\prime}_{j}}|$. Let
$\overline{c}^{\prime}\coloneqq(c^{\prime}_{1},\ldots,c^{\prime}_{d^{\prime}})$
and
$\overline{m}^{\prime}\coloneqq(m^{\prime}_{1},\ldots,m^{\prime}_{d^{\prime}})$.
Note that $\sum_{j\in[d^{\prime}]}c^{\prime}_{j}m^{\prime}_{j}=n$. Hence
$(\overline{c}^{\prime},\overline{m}^{\prime})\in\textit{Seg}(n)$ is a
segmentation of $n$ of size
$c^{\prime}\coloneqq\sum_{j=1}^{d^{\prime}}c^{\prime}_{j}$ and of degree
$d^{\prime}$.

Note that
$\mathcal{I}_{L^{\prime}}\models\varphi_{\overline{c}^{\prime},\overline{m}^{\prime}}$.
Furthermore, for every $m\in\mathbb{N}_{\scriptscriptstyle\geqslant 1}$ we
have: $\mathcal{I}_{L^{\prime}}\models\varphi_{\tilde{L},m}$ $\iff$
$(\overline{m}^{\prime},\overline{c}^{\prime})\in\textit{Seg}(m)$ $\iff$
$m=n=\operatorname{hom}(\tilde{L},L^{\prime})$. This verifies that for every
$m\geqslant 1$ the formula $\varphi_{\tilde{L},m}$ has the desired properties.

3) Let $\tilde{L}\coloneqq L\langle{X_{b}}{\to}\bullet\rangle$ for some
${X_{b}}\subseteq\operatorname{dom}(b)\setminus\operatorname{img}(g)$. If
${X_{b}}=\varnothing$ we are done since $\tilde{L}=L$. If
${X_{b}}\neq\varnothing$ let $\ell\coloneqq|{X_{b}}|$ and let
${X_{b}}=\\{i_{1},\ldots,i_{\ell}\\}$ with $i_{1}<\cdots<i_{\ell}$. Note that
$\tilde{r}=r$, $\tilde{b}=b-{X_{b}}$, and $\tilde{g}=g$. We let

$\varphi_{\tilde{L},0}\ \ \coloneqq\ \
\forall(\texttt{{e}}_{i_{1}},\dots,\texttt{{e}}_{i_{\ell}}).(\Delta_{g}\to\varphi_{L,0})\,.$

For every $m\geqslant 1$ we let

$\varphi_{\tilde{L},m}\ \ \coloneqq\ \
\bigvee_{(\overline{c},\overline{m})\in\textit{Seg}(m)}\varphi^{\prime}_{\overline{c},\overline{m}}$

where for every
$(\overline{c},\overline{m})=((c_{1},\ldots,c_{d}),(m_{1},\ldots,m_{d}))\in\textit{Seg}(m)$
and $c\coloneqq\sum_{i\in[d]}c_{i}$ we let

$\begin{array}[]{ll}\varphi^{\prime}_{\overline{c},\overline{m}}\ \
\coloneqq&\exists^{\scalebox{0.6}{$=$}c}(\texttt{{e}}_{i_{1}},\dots,\texttt{{e}}_{i_{\ell}}).(\Delta_{g}\land\lnot\varphi_{L,0})\
\ \land\\\\[4.30554pt]
&\bigwedge_{j\in[d]}\left(\exists^{\scalebox{0.6}{$=$}c_{j}}(\texttt{{e}}_{i_{1}},\dots,\texttt{{e}}_{i_{\ell}}).(\Delta_{g}\land\varphi_{L,m_{j}}\right)\,.\end{array}$

Let $L^{\prime}=(I^{\prime},r^{\prime},b^{\prime},g^{\prime})$ satisfy the
lemma’s assumptions for $\tilde{L}$ instead of $L$. I.e., we have
$\operatorname{dom}(b^{\prime})\supseteq\operatorname{dom}(\tilde{b})=\operatorname{dom}(b)\setminus{X_{b}}$,
$\operatorname{dom}(r^{\prime})\supseteq\operatorname{dom}(\tilde{r})=\operatorname{dom}(r)$,
and $L^{\prime}$ has real guards w.r.t. $\tilde{g}$. Thus,
$\mathcal{I}_{L^{\prime}}\models\Delta_{\tilde{g}}$. From Lemma 7.15 we know
that

$n\ \coloneqq\ \operatorname{hom}(\tilde{L},L^{\prime})\ \ =\sum_{\bar{e}\in
B(I^{\prime})^{\ell}}\operatorname{hom}(L,L^{\prime}\langle{X_{b}}{\to}\overline{e}\rangle).$
(10)

Note that $n=0$ $\iff$
$\operatorname{hom}(L,L^{\prime}\langle{X_{b}}{\to}\overline{e}\rangle)=0$ for
all $\bar{e}\in B(I^{\prime})^{\ell}$ $\iff$ for all $\bar{e}\in
B(I^{\prime})^{\ell}$ we have either
$\mathcal{I}_{L^{\prime}\langle{X_{b}}{\to}\overline{e}\rangle}\not\models\Delta_{g}$
or
$\mathcal{I}_{L^{\prime}\langle{X_{b}}{\to}\overline{e}\rangle}\models(\Delta_{g}\wedge\varphi_{L,0})$
$\iff$ $\mathcal{I}_{L^{\prime}}\models\varphi_{\tilde{L},0}$. Thus, the
formula $\varphi_{\tilde{L},0}$ has the desired meaning.

Let us now consider the case where $n\geqslant 1$. For every number
$m^{\prime}\in[n]$ let $S^{\prime}_{m^{\prime}}$ be the set of all $\bar{e}\in
B(I^{\prime})^{\ell}$ such that
$m^{\prime}=\operatorname{hom}(L,L^{\prime}\langle{X_{b}}{\to}\overline{e}\rangle)$.
Let $d^{\prime}$ be the number of distinct $m^{\prime}\in[n]$ for which
$S^{\prime}_{m^{\prime}}\neq\varnothing$, and let
$m^{\prime}_{1}<\cdots<m^{\prime}_{d^{\prime}}$ be an ordered list of all
$m^{\prime}\in[n]$ with $S^{\prime}_{m^{\prime}}\neq\varnothing$. For each
$j\in[d^{\prime}]$ let $c^{\prime}_{j}\coloneqq|S^{\prime}_{m^{\prime}_{j}}|$.
Let
$\overline{c}^{\prime}\coloneqq(c^{\prime}_{1},\ldots,c^{\prime}_{d^{\prime}})$
and
$\overline{m}^{\prime}\coloneqq(m^{\prime}_{1},\ldots,m^{\prime}_{d^{\prime}})$.
Note that $\sum_{j\in[d^{\prime}]}c^{\prime}_{j}m^{\prime}_{j}=n$. Hence
$(\overline{c}^{\prime},\overline{m}^{\prime})\in\textit{Seg}(n)$ is a
segmentation of $n$ of size
$c^{\prime}\coloneqq\sum_{j\in[d^{\prime}]}c^{\prime}_{j}$ and of degree
$d^{\prime}$.

Note that
$\mathcal{I}_{L^{\prime}}\models\varphi^{\prime}_{\overline{c}^{\prime},\overline{m}^{\prime}}$.
Furthermore, for every $m\in\mathbb{N}_{\scriptscriptstyle\geqslant 1}$ we
have: $\mathcal{I}_{L^{\prime}}\models\varphi_{\tilde{L},m}$ $\iff$
$(\overline{m}^{\prime},\overline{c}^{\prime})\in\textit{Seg}(m)$ $\iff$
$m=n=\operatorname{hom}(\tilde{L},L^{\prime})$. This verifies that for every
$m\geqslant 1$ the formula $\varphi_{\tilde{L},m}$ has the desired meaning.

It remains to verify that
$(\Delta_{\tilde{g}}\wedge\varphi_{\tilde{L},m})\in\textsf{{GC}}^{{k}}$ for
every $m\in\mathbb{N}$. Recall that $\tilde{g}=g$. Thus, $\tilde{g}$ satisfies
the condition (6) of rule 7) of the syntax definition of
$\textsf{{GC}}^{{k}}$. Since, by the induction hypothesis,
$(\Delta_{g}\wedge\varphi_{L,m_{j}})\in\textsf{{GC}}^{{k}}$, we obtain by rule
7) that the conjunction of $\Delta_{\tilde{g}}$ with the formula in the second
line of $\varphi^{\prime}_{\overline{c},\overline{m}}$ belongs to
$\textsf{{GC}}^{{k}}$. The same reasoning (combined with rule 4)) yields that
the conjunction of $\Delta_{\tilde{g}}$ with the formula in the first line of
$\varphi^{\prime}_{\overline{c},\overline{m}}$ belongs to
$\textsf{{GC}}^{{k}}$. Applying rule 5) yields that each formula
$(\Delta_{\tilde{g}}\wedge\varphi^{\prime}_{\overline{c},\overline{m}})$ as
well as the formula $(\Delta_{\tilde{g}}\wedge\varphi_{\tilde{L},m})$ belongs
to $\textsf{{GC}}^{{k}}$, for every $m\geqslant 1$. A similar reasoning shows
that also $(\Delta_{\tilde{g}}\wedge\varphi_{\tilde{L},0})$ belongs to
$\textsf{{GC}}^{{k}}$.

4) Let $\tilde{L}\coloneqq L[{\leadsto}f]$, where $f$ is a transition for $g$.
I.e., $\varnothing\neq\operatorname{dom}(f)\subseteq\operatorname{dom}(g)$,
such that for every $i\in\operatorname{dom}(g)$ with
$g(i)\in\operatorname{img}(f)$ we have $i\in\operatorname{dom}(f)$. By
definition,
$\tilde{L}=(M_{f}\mathbin{\cdot}L\langle{X_{b}}{\to}\bullet\rangle)$ for
${X_{b}}\coloneqq\operatorname{img}(g)\cap\operatorname{img}(f)\cap\operatorname{dom}(b)$.
In particular, $\tilde{g}=f\cup g$, i.e., $\tilde{g}(i)=f(i)$ for all
$i\in\operatorname{dom}(f)$, and $\tilde{g}(i)=g(i)$ for all
$i\in\operatorname{dom}(g)\setminus\operatorname{dom}(f)$.

Consider an arbitrary
$L^{\prime}=(I^{\prime},r^{\prime},b^{\prime},g^{\prime})$ that satisfies the
lemma’s assumptions for $\tilde{L}$ instead of $L$. I.e., we have
$\operatorname{dom}(b^{\prime})\supseteq\operatorname{dom}(\tilde{b})=\operatorname{img}(f)\cup\operatorname{dom}(b)$,
$\operatorname{dom}(r^{\prime})\supseteq\operatorname{dom}(\tilde{r})=\operatorname{dom}(f)\cup\operatorname{dom}(r)=\operatorname{dom}(f)\cup\operatorname{dom}(g)=\operatorname{dom}(\tilde{g})$,
and $L^{\prime}$ has real guards w.r.t. $\tilde{g}$. Since $L^{\prime}$ has
real guards w.r.t. $\tilde{g}$ we have
$\mathcal{I}_{L^{\prime}}\models\Delta_{\tilde{g}}$. From Lemma 7.15 we know
that $n\coloneqq\operatorname{hom}(\tilde{L},L^{\prime})=$

$\operatorname{hom}(M_{f},L^{\prime})\ \ {\cdot}\\!\\!\sum_{\bar{e}\in
B(I^{\prime})^{\ell}}\operatorname{hom}(L,L^{\prime}\langle{X_{b}}{\to}\overline{e}\rangle)$

for
${X_{b}}\coloneqq\operatorname{dom}(b)\cap\operatorname{img}(f)\cap\operatorname{img}(g)$.
Furthermore, we know that $\operatorname{hom}(M_{f},L^{\prime})\in\\{0,1\\}$.
Note that $\operatorname{hom}(M_{f},L^{\prime})=1$ $\iff$
$\mathcal{I}_{L^{\prime}}\models\Delta_{f}$. Since
$\mathcal{I}_{L^{\prime}}\models\Delta_{\tilde{g}}$ and $\tilde{g}\supseteq
f$, we obviously have $\mathcal{I}_{L^{\prime}}\models\Delta_{f}$. Thus,
$n=\sum_{\bar{e}\in
B(I^{\prime})^{\ell}}\operatorname{hom}(L,L^{\prime}\langle{X_{b}}{\to}\overline{e}\rangle)$,
as in case 3) in equation (10). We therefore can choose the exact same
formulas $\varphi_{\tilde{L},m}$ as in case 3) for all $m\in\mathbb{N}$ and
obtain that these formulas have the desired meaning.

It remains to verify that
$(\Delta_{\tilde{g}}\wedge\varphi_{\tilde{L},m})\in\textsf{{GC}}^{{k}}$ for
every $m\in\mathbb{N}$. Note that now we have $\tilde{g}=f\cup g$ (whereas in
case 3) we had to deal with the case where $\tilde{g}=g$). All we have to do
is argue that $\tilde{g}$ satisfies the condition (6) of rule 7) of the syntax
definition of $\textsf{{GC}}^{{k}}$. Once having achieved this, the same
reasoning as in case 3) proves that the formula
$(\Delta_{\tilde{g}}\wedge\varphi_{\tilde{L},m})$ belongs to
$\textsf{{GC}}^{{k}}$ for every $m\in\mathbb{N}$.

Note that according to the induction hypothesis, for all
$m^{\prime}\in\mathbb{N}$ we have:
$\operatorname{dom}(b)=\textit{ifree}_{B}((\Delta_{g}\wedge\varphi_{L,m^{\prime}}))\supseteq\operatorname{img}(g)$.
Therefore, ${X_{b}}=\operatorname{img}(f)\cap\operatorname{img}(g)$.

Consider an arbitrary $i\in\operatorname{dom}(g)$. We have to show that
$\tilde{g}(i)=g(i)$ or $\tilde{g}(i)\in{X_{b}}$ or
$\tilde{g}(i)\not\in\operatorname{img}(g)$.

If $\tilde{g}(i)=g(i)$ or $\tilde{g}(i)\not\in\operatorname{img}(g)$, we are
done. Consider the case that $\tilde{g}(i)\neq g(i)$ and
$\tilde{g}(i)\in\operatorname{img}(g)$. In this case, $\tilde{g}(i)=f(i)$ and
there exists an $i^{\prime}\in\operatorname{dom}(g)$ with
$g(i^{\prime})=\tilde{g}(i)=f(i)$. Hence,
$\tilde{g}(i)\in\operatorname{img}(f)\cap\operatorname{img}(g)={X_{b}}$, and
we are done.

5) Let $\tilde{L}\coloneqq(L_{1}\mathbin{\cdot}L_{2})$. Recall from the
inductive step’s assumption that the lemma’s statement is already shown for
$L_{i}=(I_{i},r_{i},b_{i},g_{i})$ for each $i\in[2]$ and that $g_{1},g_{2}$
are compatible. Recall from Definition 7.5 that
$\tilde{L}=(\tilde{I},\tilde{r},\tilde{b},\tilde{g})$ with
$\operatorname{dom}(\tilde{r})=\operatorname{dom}(r_{1})\cup\operatorname{dom}(r_{2})$,
$\operatorname{dom}(\tilde{b})=\operatorname{dom}(b_{1})\cup\operatorname{dom}(b_{2})$,
and $\tilde{g}=g_{1}\cup g_{2}$. We let

$\varphi_{\tilde{L},0}\ \ \coloneqq\ \ \big{(}\,\varphi_{L_{1},0}\ \vee\
\varphi_{L_{2},0}\,\big{)}\,.$

For each $m\geqslant 1$ we let $S_{m}$ be the set of all tuples
$(m_{1},m_{2})$ of positive integers such that $m_{1}\cdot m_{2}=m$ (note that
$S_{m}$ is finite and non-empty), and let

$\varphi_{\tilde{L},m}\ \ \coloneqq\ \ \bigvee_{(m_{1},m_{2})\in
S_{m}}\big{(}\,\varphi_{L_{1},m_{1}}\ \wedge\
\varphi_{L_{2},m_{2}}\,\big{)}\,.$

By the induction hypothesis we know that
$(\Delta_{g_{i}}\wedge\varphi_{L_{i},m_{i}})\in\textsf{{GC}}^{{k}}$ for each
$i\in[2]$ and every $m_{i}\in\mathbb{N}$. Since $\tilde{g}=g_{1}\cup g_{2}$
and $g_{1},g_{2}$ are compatible, we obtain that the formula
$(\Delta_{\tilde{g}}\wedge\varphi_{\tilde{L},m})$ belongs to
$\textsf{{GC}}^{{k}}$ for every $m\in\mathbb{N}$.

All that remains to be done is to show that these formulas have the desired
meaning. Consider an arbitrary
$L^{\prime}=(I^{\prime},r^{\prime},b^{\prime},g^{\prime})$ that satisfies the
lemma’s assumptions for $\tilde{L}$ instead of $L$. I.e., we have
$\operatorname{dom}(b^{\prime})\supseteq\operatorname{dom}(\tilde{b})=\operatorname{dom}(b_{1})\cup\operatorname{dom}(b_{2})$,
$\operatorname{dom}(r^{\prime})\supseteq\operatorname{dom}(\tilde{r})=\operatorname{dom}(b_{1})\cup\operatorname{dom}(b_{2})$,
and $g^{\prime}\supseteq\tilde{g}=g_{1}\cup g_{2}$.

Since $L^{\prime}$ has real guards w.r.t. $\tilde{g}$ we have
$\mathcal{I}_{L^{\prime}}\models\Delta_{\tilde{g}}$. From Lemma 7.15 we know
that

$n\ \coloneqq\ \operatorname{hom}(\tilde{L},L^{\prime})\ =\
\operatorname{hom}(L_{1},L^{\prime})\cdot\operatorname{hom}(L_{2},L^{\prime})\,.$
(11)

Note that $n=0$ $\iff$ $\operatorname{hom}(L_{1},L^{\prime})=0$ or
$\operatorname{hom}(L_{2},L^{\prime})=0$. Thus,
$\mathcal{I}_{L^{\prime}}\models\varphi_{\tilde{L},0}$ $\iff$ $n=0$. Hence,
the formula $\varphi_{\tilde{L},0}$ has the desired meaning.

Let us now consider the case where $n\geqslant 1$. For $i\in[2]$ let
$n_{i}\coloneqq\operatorname{hom}(L_{i},L^{\prime})$. By (11) we have
$n=n_{1}\cdot n_{2}$. Thus, $(n_{1},n_{2})\in S_{n}$. Note for every
$m\geqslant 1$ that $\mathcal{I}_{L^{\prime}}\models\varphi_{\tilde{L},m}$
$\iff$ $(n_{1},n_{2})\in S_{m}$ $\iff$ $n=n_{1}\cdot n_{2}=m$ $\iff$
$\operatorname{hom}(\tilde{L},L^{\prime})=m$. Hence, for every $m\geqslant 1$
the formula $\varphi_{\tilde{L},m}$ has the desired meaning. This completes
the proof of Lemma 8.1. ∎

###  E.2 Complete proof of Lemma 8.2

######  Proof of Lemma 8.2.

We proceed by induction on the construction of $\chi$.

Base cases: $\chi$ is $(\Delta_{g}\land\psi)$ and matches one of the
following:

  1. Case 1:

$\psi$ is $E(\texttt{{e}}_{j},\texttt{{v}}_{i})$ and
$\operatorname{dom}(g)=\\{i\\}$ and $j\in[k]$. Note that
$\chi=(E(\texttt{{e}}_{g(i)},\texttt{{v}}_{i})\wedge
E(\texttt{{e}}_{j},\texttt{{v}}_{i}))$. Let $I$ be the incidence graph defined
as follows. $I$ has exactly one red node, i.e., $R(I)=\\{v_{i}\\}$. If
$g(i)=j$ then $I$ has exactly one blue node, i.e., $B(I)=\\{e_{j}\\}$;
otherwise $I$ has exactly two blue nodes, i.e., $B(I)=\\{e_{j},e_{g(i)}\\}$.
$I$ has edges from every blue node to the red node, i.e., $E(I)=B(I)\times
R(I)$. Consider the $k$-labeled incidence graph $L=(I,r,b,g)$ where
$\operatorname{dom}(r)=\\{i\\}$ and $r(i)=v_{i}$, and
$\operatorname{dom}(b)=\\{j,g(i)\\}$ and $b(j)=e_{j}$ and $b(g(i))=e_{g(i)}$
(and $g$ is the formula $\chi$’s guard function). Note that
$L\in\textsl{GLI}_{k}$ (use the base case of Definition 7.10). For every
$k$-labeled incidence graph $L^{\prime}$ we have:
$\operatorname{hom}(L,L^{\prime})\in\\{0,1\\}$, and
$\operatorname{hom}(L,L^{\prime})=1$ $\iff$
$\mathcal{I}_{L^{\prime}}\models\chi$. Thus we are done by choosing
$Q\coloneqq L$.

  2. Case 2:

$\psi$ is $\texttt{{e}}_{j}{=}\texttt{{e}}_{j^{\prime}}$ and
$\operatorname{dom}(g)=\varnothing$ and $j,j^{\prime}\in[k]$. Note that
$\chi=(\top\wedge\texttt{{e}}_{j}{=}\texttt{{e}}_{j^{\prime}})$. Let $I$ be
the incidence graph with no red node and exactly one blue node, i.e.,
$R(I)=\varnothing$, $B(I)=\\{e\\}$, and $E(I)=\varnothing$. Consider the
$k$-labeled incidence graph $L=(I,r,b,g)$ where
$\operatorname{dom}(r)=\varnothing$,
$\operatorname{dom}(b)=\\{j,j^{\prime}\\}$ and $b(j)=b(j^{\prime})=e$ (and $g$
is the formula $\chi$’s (empty) guard function). Note that
$L\in\textsl{GLI}_{k}$ (use the base case of Definition 7.10). For every
$k$-labeled incidence graph $L^{\prime}$ we have:
$\operatorname{hom}(L,L^{\prime})\in\\{0,1\\}$, and
$\operatorname{hom}(L,L^{\prime})=1$ $\iff$
$\mathcal{I}_{L^{\prime}}\models\chi$. Thus we are done by choosing
$Q\coloneqq L$.

  3. Case 3:

$\psi$ is $\texttt{{v}}_{i}{=}\texttt{{v}}_{i^{\prime}}$ with
$\operatorname{dom}(g)=\\{i,i^{\prime}\\}$. Note that
$\chi=(E(\texttt{{e}}_{g(i)},\texttt{{v}}_{i})\wedge
E(\texttt{{e}}_{g(i^{\prime})},\texttt{{v}}_{i^{\prime}})\wedge\texttt{{v}}_{i}{=}\texttt{{v}}_{i^{\prime}})$.
Let $I$ be the incidence graph defined as follows. $I$ has exactly one red
node, i.e., $R(I)=\\{v\\}$. If $g(i)=g(i^{\prime})$ then $I$ has exactly one
blue node, i.e., $B(I)=\\{e\\}$; otherwise $I$ has exactly two blue nodes,
i.e., $B(I)=\\{e_{g(i)},e_{g(i^{\prime})}\\}$. $I$ has edges from every blue
node to the red node, i.e., $E(I)=B(I)\times R(I)$. Consider the $k$-labeled
incidence graph $L=(I,r,b,g)$ where $g$ is the formula $\chi$’s guard
function, and $\operatorname{dom}(r)=\\{i,i^{\prime}\\}$ and
$r(i)=r(i^{\prime})=v$, and $\operatorname{dom}(b)=\\{g(i),g(i^{\prime})\\}$.
In case that $g(i)=g(i^{\prime})$ we have $b(g(i))=e$, and otherwise we have
$b(g(i))=e_{g(i)}$ and $b(g(i^{\prime}))=e_{g(i^{\prime})}$. Note that
$L\in\textsl{GLI}_{k}$ (use the base case of Definition 7.10). For every
$k$-labeled incidence graph $L^{\prime}$ we have:
$\operatorname{hom}(L,L^{\prime})\in\\{0,1\\}$, and
$\operatorname{hom}(L,L^{\prime})=1$ $\iff$
$\mathcal{I}_{L^{\prime}}\models\chi$. Thus we are done by choosing
$Q\coloneqq L$.

  4. Special Case:

$\psi$ is unfulfillable for all $k$-labeled incidence graphs $L^{\prime}$
matching the requirements imposed by the lemma.

If $\operatorname{dom}(g)\neq\varnothing$ we choose $L\coloneqq M_{g}$ and
$Q\coloneqq 0{\cdot}L$. Note that $Q\in\textsl{QGLI}_{k}$ and
$g_{Q},\textup{db}_{Q},\textup{dr}_{Q}$ are as required by the lemma.
Furthermore, $\operatorname{hom}(Q,L^{\prime})=0$ for every $k$-labeled
incidence graph $L^{\prime}$.

If $\operatorname{dom}(g)=\varnothing$ and
$\operatorname{free}(\chi)\neq\varnothing$ we choose $I$ to consist of a
single blue node $e$ and no red nodes, and we let $L=(I,r,b,g)$ with
$\operatorname{dom}(r)=\operatorname{dom}(g)=\varnothing$ and
$\operatorname{dom}(b)=\textit{ifree}_{B}(\chi)$ and $b(j)=e$ for every
$j\in\textit{ifree}_{B}(\chi)$. Let $Q\coloneqq 0{\cdot}L$. Note that
$Q\in\textsl{QGLI}_{k}$ and $g_{Q},\textup{db}_{Q},\textup{dr}_{Q}$ are as
required by the lemma. Furthermore, $\operatorname{hom}(Q,L^{\prime})=0$ for
every $k$-labeled incidence graph $L^{\prime}$.

If $\operatorname{dom}(g)=\varnothing$ and
$\operatorname{free}(\chi)=\varnothing$ we choose $I$ to be empty, i.e.,
$R(I)=B(I)=E(I)=\varnothing$, and we let $L=(I,r,b,g)$ with
$\operatorname{dom}(r)=\operatorname{dom}(b)=\operatorname{dom}(g)=\varnothing$.
Let $Q\coloneqq 0{\cdot}L$. Note that $Q\in\textsl{QGLI}_{k}$ and
$g_{Q},\textup{db}_{Q},\textup{dr}_{Q}$ are as required by the lemma.
Furthermore, $\operatorname{hom}(Q,L^{\prime})=0$ for every $k$-labeled
incidence graph $L^{\prime}$.

Inductive step: We assume that the lemma’s statement is already shown for
$\chi\coloneqq(\Delta_{g}\wedge\psi)\in\textsf{{GC}}^{{k}}$ and for
$\chi_{i}\coloneqq(\Delta_{g_{i}}\wedge\psi_{i})\in\textsf{{GC}}^{{k}}$ for
$i\in[2]$, where $g_{1},g_{2}$ are compatible.

Fix arbitrary $m,d\in\mathbb{N}$ with $m\geqslant 1$. Let
$Q,Q_{1},Q_{2}\in\textsl{QGLI}_{k}$ be the quantum incidence graphs provided
by the lemma’s statement for $\chi,\chi_{1},\chi_{2}$ and the parameters
$m,d$.

Our goal is to prove the lemma’s statement for parameters $m,d$ and the
particular
$\tilde{\chi}\coloneqq(\Delta_{\tilde{g}}\land\tilde{\psi})\in\textsf{{GC}}^{{k}}$
considered in the following case distinction. We will write $\tilde{Q}$ to
denote the quantum incidence graph that has to be constructed for
$\tilde{\chi}$.

  1. Case 4:

$\tilde{\psi}=\lnot\psi$ and $\tilde{g}=g$. We choose $\tilde{Q}\coloneqq
Q[\\{1\\},\\{0\\}]$ according to Lemma 7.16. Note that
$\tilde{Q}\in\textsl{QGLI}_{k}$ and $\tilde{Q}$ has the parameters
$g_{\tilde{Q}},\textup{db}_{\tilde{Q}},\textup{dr}_{\tilde{Q}}$ required by
the lemma. Furthermore, for all $k$-labeled incidence graphs $L^{\prime}$
satisfying the lemma’s assumptions we have:
$\mathcal{I}_{L^{\prime}}\models\Delta_{g}$ and
$\operatorname{hom}(\tilde{Q},L^{\prime})\in\\{0,1\\}$. Furthermore,
$\operatorname{hom}(\tilde{Q},L^{\prime})=1$ $\iff$
$\operatorname{hom}(Q,L^{\prime})=0$ $\iff$
$\mathcal{I}_{L^{\prime}}\not\models\chi$. Since
$\mathcal{I}_{L^{\prime}}\models\Delta_{g}$ by assumption, we have:
$\mathcal{I}_{L^{\prime}}\not\models\chi$ $\iff$
$\mathcal{I}_{L^{\prime}}\not\models\psi$ $\iff$
$\mathcal{I}_{L^{\prime}}\models\neg\psi$ $\iff$
$\mathcal{I}_{L^{\prime}}\models\tilde{\chi}$. This completes Case 4.

  2. Case 5:

$\tilde{\psi}=(\psi_{1}\land\psi_{2})$ and $\tilde{g}=g_{1}\cup g_{2}$ (recall
that $g_{1}$ and $g_{2}$ are compatible). We choose
$\tilde{Q}\coloneqq(Q_{1}\mathbin{\cdot}Q_{2})$. Note that
$\tilde{Q}\in\textsl{QGLI}_{k}$ and $\tilde{Q}$ has the parameters
$g_{\tilde{Q}},\textup{db}_{\tilde{Q}},\textup{dr}_{\tilde{Q}}$ required by
the lemma.

Consider an arbitrary $k$-labeled incidence graph $L^{\prime}$ satisfying the
lemma’s assumptions. By Lemma 7.15 we have
$\operatorname{hom}(\tilde{Q},L^{\prime})=\operatorname{hom}(Q_{1},L^{\prime})\cdot\operatorname{hom}(Q_{2},L^{\prime})$.
By the induction hypothesis we know for each $i\in[2]$ that
$\operatorname{hom}(Q_{i},L^{\prime})\in\\{0,1\\}$; and
$\operatorname{hom}(Q_{i},L^{\prime})=1$ $\iff$
$\mathcal{I}_{L^{\prime}}\models\chi_{i}$. Thus,
$\operatorname{hom}(\tilde{Q},L^{\prime})\in\\{0,1\\}$. Furthermore,
$\operatorname{hom}(\tilde{Q},L^{\prime})=1$ $\iff$
$\mathcal{I}_{L^{\prime}}\models\chi_{1}$ and
$\mathcal{I}_{L^{\prime}}\models\chi_{2}$ $\iff$
$\mathcal{I}_{L^{\prime}}\models\tilde{\chi}$. This completes Case 5.

  3. Case 6:

$\tilde{\psi}=\exists^{\scalebox{0.6}{$\geqslant$}n}(\texttt{{v}}_{i_{1}},\ldots,\texttt{{v}}_{i_{\ell}}).(\Delta_{g}\land\psi)$
and $\tilde{g}=g-\\{i_{1},\ldots,i_{\ell}\\}$ and
$n,\ell\in\mathbb{N}_{\scriptscriptstyle\geqslant 1}$ and
$i_{1}<\cdots<i_{\ell}$ and
${X_{r}}\coloneqq\\{i_{1},\ldots,i_{\ell}\\}\subseteq\operatorname{dom}(g)$.

If $n>(md)^{\ell}$, the formula $\tilde{\psi}$ is unfulfillable for all
$k$-labeled incidence graphs $L^{\prime}$ matching the requirements imposed by
the lemma (simply because each such $L^{\prime}$ has at most $md$ red nodes).
Thus, we are done by choosing $\tilde{Q}$ according to the “special case”
handled above.

If $n\leqslant(md)^{\ell}$, we proceed as follows. Let $Q^{\prime}\coloneqq
Q[{X_{r}}{\to}\bullet]$ and $\tilde{Q}\coloneqq Q^{\prime}[X,Y]$ for
$X\coloneqq\\{0,\ldots,n{-}1\\}$ and $Y\coloneqq\\{n,\ldots,(md)^{\ell}\\}$.
Note that $Q^{\prime}\in\textsl{QGLI}_{k}$ and
$\tilde{Q}\in\textsl{QGLI}_{k}$, and $\tilde{Q}$ has the parameters
$g_{\tilde{Q}},\textup{db}_{\tilde{Q}},\textup{dr}_{\tilde{Q}}$ required by
the lemma. Consider an arbitrary $k$-labeled incidence graph $L^{\prime}$
satisfying the lemma’s assumptions for $\tilde{\chi}$. In particular,
$L^{\prime}$ has real guards w.r.t. $\tilde{g}$ and therefore satisfies
$\Delta_{\tilde{g}}$. Thus, $\mathcal{I}_{L^{\prime}}\models\tilde{\chi}$
$\iff$ $\mathcal{I}_{L^{\prime}}\models\tilde{\psi}$. By Lemma 7.15 we have

$\operatorname{hom}(Q^{\prime},L^{\prime})\ =\ \sum_{\overline{v}\in
R(I_{L^{\prime}})^{\ell}}\operatorname{hom}(Q,L^{\prime}[{X_{r}}{\to}\overline{v}])\,.$

Consider an arbitrary $\overline{v}$ with
$\operatorname{hom}(Q,L^{\prime}[{X_{r}}{\to}\overline{v}])>0$. Since $Q$ has
real guards, the $k$-labeled incidence graph
$L^{\prime}[{X_{r}}{\to}\overline{v}]$ satisfies the lemma’s assumptions
w.r.t. the formula $\chi$ (in particular, it has real guards w.r.t. $g$).
Therefore, by the induction hypothesis we obtain that
$\operatorname{hom}(Q,L^{\prime}[{X_{r}}{\to}\overline{v}])=1$ and
$\mathcal{I}_{L^{\prime}[{X_{r}}{\to}\overline{v}]}\models\chi$.

Therefore,
$\operatorname{hom}(Q^{\prime},L^{\prime})\leqslant|R(I_{L^{\prime}})|^{\ell}\leqslant(md)^{\ell}$.
Moreover, $\operatorname{hom}(Q^{\prime},L^{\prime})$ is exactly the number of
tuples $\overline{v}\in R(I_{L^{\prime}})^{\ell}$ such that
$\mathcal{I}_{L^{\prime}[{X_{r}}{\to}\overline{v}]}\models\chi$.

By our choice of $X,Y$ and $\tilde{Q}=Q^{\prime}[X,Y]$ we obtain that
$\operatorname{hom}(\tilde{Q},L^{\prime})\in\\{0,1\\}$ and, moreover,
$\operatorname{hom}(\tilde{Q},L^{\prime})=1$ $\iff$
$\mathcal{I}_{L^{\prime}}\models\tilde{\chi}$. This completes Case 6.

  4. Case 7:

$\tilde{\psi}=\exists^{\scalebox{0.6}{$\geqslant$}n}(\texttt{{e}}_{i_{1}},\ldots,\texttt{{e}}_{i_{\ell}}).(\Delta_{g}\land\psi)$
and $\tilde{g}$, where $n,\ell\in\mathbb{N}_{\scriptscriptstyle\geqslant 1}$
and $S\coloneqq\\{i_{1},\ldots,i_{\ell}\\}\subseteq\textit{ifree}_{B}(\chi)$
for $\chi\coloneqq(\Delta_{g}\wedge\psi)$ with $i_{1}<\cdots<i_{\ell}$ and
$\operatorname{dom}(\tilde{g})=\operatorname{dom}(g)$ and all
$i\in\operatorname{dom}(g)$ satisfy

$\tilde{g}(i)=g(i)\quad\text{or}\quad\tilde{g}(i)\in
S\quad\text{or}\quad\tilde{g}(i)\not\in\operatorname{img}(g).$ (12)

If $n>m^{\ell}$, the formula $\tilde{\psi}$ is unfulfillable for all
$k$-labeled incidence graphs $L^{\prime}$ matching the requirements imposed by
the lemma (simply because each such $L^{\prime}$ has only $m$ blue nodes).
Thus, we are done by choosing $\tilde{Q}$ according to the “special case”
handled above.

If $n\leqslant m^{\ell}$, we proceed as follows. Since $Q$ is obtained by the
induction hypothesis, we know in particular that $g_{Q}=g$,
$\textup{db}_{Q}=\textit{ifree}_{B}(\chi)$, and
$\textup{dr}_{Q}=\operatorname{dom}(g)=\textit{ifree}_{R}(\chi)$. In
particular, we have: $S\subseteq\textup{db}_{Q}$.

Claim 1: Consider an arbitrary $k$-labeled incidence graph $L^{\prime}$
satisfying the lemma’s assumptions for $\tilde{\chi}$. For

$\textit{num}(L^{\prime})\ \coloneqq\ \operatorname{hom}(Q\langle
S{\to}\bullet\rangle,L^{\prime})$

we have: $\textit{num}(L^{\prime})=\sum_{\overline{e}\in
B(I_{L^{\prime}})^{\ell}}\operatorname{hom}(Q,L^{\prime}\langle
S{\to}\overline{e}\rangle)$ and
$0\leqslant\textit{num}(L^{\prime})\leqslant|B(I_{L^{\prime}})|^{\ell}$ and
$\textit{num}(L^{\prime})$ is exactly the number of tuples $\overline{e}\in
B(I_{L^{\prime}})^{\ell}$ such that
$\mathcal{I}_{L^{\prime}\langle{X_{b}}{\to}\overline{e}\rangle}\models\chi$.

Proof of Claim 1: Since $L^{\prime}$ satisfies the lemma’s assumptions for
$\tilde{\chi}$, it has real guards w.r.t. $\tilde{g}$ and therefore satisfies
$\Delta_{\tilde{g}}$. Thus, $\mathcal{I}_{L^{\prime}}\models\tilde{\chi}$
$\iff$ $\mathcal{I}_{L^{\prime}}\models\tilde{\psi}$.

Furthermore, $\textup{db}_{Q}=\textit{ifree}_{B}(\chi)\supseteq S$. Lemma 7.15
yields:

$\textit{num}(L^{\prime})\ =\ \sum_{\overline{e}\in
B(I_{L^{\prime}})^{\ell}}\\!\\!\\!\operatorname{hom}(Q,L^{\prime}\langle
S{\to}\overline{e}\rangle)\,.$

Consider an arbitrary $\overline{e}$ with
$\operatorname{hom}(Q,L^{\prime}\langle S{\to}\overline{e}\rangle)>0$. Since
$Q$ has real guards, the $k$-labeled incidence graph $L^{\prime}\langle
S{\to}\overline{e}\rangle$ satisfies the lemma’s assumptions w.r.t. the
formula $\chi$ (in particular, it has real guards w.r.t. $g_{Q}=g$).
Therefore, by the induction hypothesis we obtain that
$\operatorname{hom}(Q,L^{\prime}\langle S{\to}\overline{e}\rangle)=1$ and
$\mathcal{I}_{L^{\prime}\langle S{\to}\overline{e}\rangle}\models\chi$.

Hence,
$0\leqslant\textit{num}(L^{\prime})\leqslant|B(I_{L^{\prime}})|^{\ell}\leqslant
m^{\ell}$. Moreover, $\textit{num}(L^{\prime})$ is exactly the number of
tuples $\overline{e}\in B(I_{L^{\prime}})^{\ell}$ such that
$\mathcal{I}_{L^{\prime}\langle{X_{b}}{\to}\overline{e}\rangle}\models\chi$.
This completes the proof of Claim 1. ∎${}_{\textit{Claim 1}}$

For the remaining parts of the proof, our aim is to

$\begin{array}[]{l}\parbox{341.43306pt}{construct a
$Q^{\prime}\in\textsl{QGLI}_{k}$ that has the parameters
$g_{\tilde{Q}},\textup{db}_{\tilde{Q}},\textup{dr}_{\tilde{Q}}$ required by
the lemma for formula $\tilde{\chi}$, such that
$\operatorname{hom}(Q^{\prime},L^{\prime})=\textit{num}(L^{\prime})$ for all
$k$-labeled incidence graphs $L^{\prime}$ satisfying the lemma's assumptions
for $\tilde{\chi}$.}\end{array}$ (13)

Once having achieved this, we can use Lemma 7.16 to obtain a $k$-labeled
quantum incidence graph $\tilde{Q}\coloneqq
Q^{\prime}[X,Y]\in\textsl{QGLI}_{k}$ for $X\coloneqq\\{0,\ldots,n{-}1\\}$ and
$Y\coloneqq\\{n,\ldots,m^{\ell}\\}$ such that
$\operatorname{hom}(\tilde{Q},L^{\prime})\in\\{0,1\\}$ and, moreover,
$\operatorname{hom}(\tilde{Q},L^{\prime})=1$ $\iff$
$\textit{num}(L^{\prime})\geqslant n$ $\iff$
$\mathcal{I}_{L^{\prime}}\models\tilde{\chi}$.

Hence, all that remains to be done to finish the proof is to achieve (13). We
let

$Z\ \coloneqq\ \\{\,i\in\operatorname{dom}(g)\ :\ \tilde{g}(i)\neq g(i)\text{
\ or \ }g(i)\in S\,\\}\,.$ (14)

If $Z=\varnothing$, we have $\tilde{g}=g$ and $\operatorname{img}(g)\cap
S=\varnothing$. Hence,
$S\subseteq\textup{db}_{Q}\setminus\operatorname{img}(g)$. Using part 3) of
Definition 7.10 we obtain that $Q^{\prime}\coloneqq Q\langle
S{\to}\bullet\rangle$ is in $\textsl{QGLI}_{k}$. Note that $Q^{\prime}$ has
the parameters $g_{\tilde{Q}},\textup{db}_{\tilde{Q}},\textup{dr}_{\tilde{Q}}$
required by the lemma for formula $\tilde{\chi}$. Furthermore, as stated in
Claim 1, we have
$\textit{num}(L^{\prime})=\operatorname{hom}(Q^{\prime},L^{\prime})$ for all
$k$-labeled incidence graphs $L^{\prime}$ satisfying the lemma’s assumptions
for $\tilde{\chi}$. Thus, we have achieved (13), and therefore the proof is
finished in case that $Z=\varnothing$.

If $Z\neq\varnothing$, we cannot simply choose $Q^{\prime}$ as above, because
there is no guarantee that $Q\langle S{\to}\bullet\rangle$ belongs to
$\textsl{QGLI}_{k}$. Instead, we proceed as follows.
Let $f$ be the partial function with $\operatorname{dom}(f)=Z$ and

$f(i)\coloneqq\tilde{g}(i)\quad\text{for all $i\in\operatorname{dom}(f)$.}$

Claim 2: 1.) $\tilde{g}=f\cup g$.
2.) $f$ is a transition for $g$.
3.) All $i\in\operatorname{dom}(f)$ satisfy: $f(i)\in S$ or
$f(i)\not\in\operatorname{img}(g)$.

Proof of Claim 2:
1.) For all $i\in\operatorname{dom}(f)$ we have: $(f\cup
g)(i)=f(i)=\tilde{g}(i)$.
For all $i\in\operatorname{dom}(g)\setminus\operatorname{dom}(f)$ we have
$(f\cup g)(i)=g(i)$. Since $i\not\in\operatorname{dom}(f)=Z$, we have
$\tilde{g}(i)=g(i)$. I.e., $(f\cup g)=\tilde{g}$.

2.) Consider an arbitrary $i\in\operatorname{dom}(g)$ with
$g(i)\in\operatorname{img}(f)$. We have to show that
$i\in\operatorname{dom}(f)$, i.e., $i\in Z$. Since
$g(i)\in\operatorname{img}(f)$, there is a $j\in Z$ such that $g(i)=f(j)$.
From (12) we know that $\tilde{g}(j)=g(j)$ or $\tilde{g}(j)\in S$ or
$\tilde{g}(j)\not\in\operatorname{img}(g)$. But

$\tilde{g}(j)\ =\ (f\cup g)(j)\ =\ f(j)\ =\ g(i)\,,$ (15)

hence $\tilde{g}(j)\in\operatorname{img}(g)$. This leaves us with two
remaining cases: $\tilde{g}(j)=g(j)$ or $\tilde{g}(j)\in S$.

In case that $\tilde{g}(j)=g(j)$, from the fact that $j\in Z$ we obtain (by
the definition of $Z$) that $g(j)\in S$. Hence,
$g(j)=\tilde{g}(j)=f(j)=g(i)\in S$. Thus, by our choice of $Z$ we have: $i\in
Z=\operatorname{dom}(f)$.

In case that $\tilde{g}(j)\in S$, by (15) we have: $\tilde{g}(j)=f(j)=g(i)\in
S$. Thus, by our choice of $Z$ we have: $i\in Z=\operatorname{dom}(f)$.

Hence, we have shown that $f$ is a transition for $g$.

3.) Consider an arbitrary $i\in\operatorname{dom}(f)$. By definition we have
$f(i)=\tilde{g}(i)$.

In case that $\tilde{g}(i)=g(i)$, by definition of $Z$ we obtain: $g(i)\in S$.
Hence, $g(i)=\tilde{g}(i)=f(i)\in S$.

In case that $\tilde{g}(i)\neq g(i)$, by (12) we know that $\tilde{g}(i)\in S$
or $\tilde{g}(i)\not\in\operatorname{img}(g)$. Since $f(i)=\tilde{g}(i)$, we
hence have: $f(i)\in S$ or $f(i)\not\in\operatorname{img}(g)$.

This completes the proof of Claim 2. ∎${}_{\textit{Claim 2}}$

Let
$D_{1}\coloneqq(S\cap\operatorname{img}(f))\setminus\operatorname{img}(g)$,
let $D_{2}\coloneqq S\setminus\operatorname{img}(\tilde{g})$, and let
$D_{3}\coloneqq\operatorname{img}(g)\cap\operatorname{img}(f)$.

_Claim 3:_ $D_{1},D_{2},D_{3}$ are pairwise disjoint, and
$S=\bigcup_{i\in[3]}D_{i}$.

_Proof of Claim 3:_ We first show that $D_{1},D_{2},D_{3}$ are pairwise
disjoint: $D_{1}\cap D_{2}=\varnothing$ because
$D_{1}\subseteq\operatorname{img}(f)\subseteq\operatorname{img}(\tilde{g})$.
$D_{1}\cap D_{3}=\varnothing$ because $D_{3}\subseteq\operatorname{img}(g)$.
$D_{2}\cap D_{3}=\varnothing$ because
$D_{3}\subseteq\operatorname{img}(f)\subseteq\operatorname{img}(\tilde{g})$.

We next show that $\bigcup_{i\in[3]}D_{i}\subseteq S$: By definition,
$D_{i}\subseteq S$ for each $i\in[2]$. For showing that $D_{3}\subseteq S$
consider an arbitrary $j\in
D_{3}=\operatorname{img}(g)\cap\operatorname{img}(f)$. Since
$j\in\operatorname{img}(f)$, there is an $i\in\operatorname{dom}(f)=Z$ such
that $j=f(i)$. From Claim 2, part 3.) we obtain that $f(i)\in S$ or
$f(i)\not\in\operatorname{img}(g)$. Since $f(i)=j\in\operatorname{img}(g)$, we
hence have $j\in S$.

Finally, we show that $S\subseteq\bigcup_{i\in[3]}D_{i}$: Consider an
arbitrary $j\in S$. If $j\in D_{2}$, we are done. If $j\not\in D_{2}$, then
$j\in\operatorname{img}(\tilde{g})$. Hence, there is an
$i\in\operatorname{dom}(\tilde{g})$ such that $j=\tilde{g}(i)$. We obtain:
$i\in Z$ (the reasoning is as follows: If $g(i)\neq\tilde{g}(i)$, then $i\in
Z$ by (14). Otherwise, $g(i)=\tilde{g}(i)=j\in S$, and by (14) we obtain that
$i\in Z$). Hence, $i\in Z=\operatorname{dom}(f)$. Thus
$j=f(i)\in\operatorname{img}(f)$. If $j\in\operatorname{img}(g)$ then $j\in
D_{3}$. Otherwise, $j\not\in\operatorname{img}(g)$, and hence $j\in D_{1}$.
∎${}_{\textit{Claim~{}3}}$

We let $Q_{1}\coloneqq Q\langle D_{1}{\to}\bullet\rangle$ and $Q_{2}\coloneqq
Q_{1}[{\leadsto}f]$ and $Q^{\prime}\coloneqq Q_{2}\langle
D_{2}{\to}\bullet\rangle$.

_Claim 4:_ $Q_{1},Q_{2},Q^{\prime}\in\textsl{QGLI}_{k}$ and $g_{Q_{1}}=g$,
$\textup{db}_{Q_{1}}=(\textup{db}_{Q}\setminus D_{1})$ and
$g_{Q^{\prime}}=\tilde{g}$,
$\textup{dr}_{Q^{\prime}}=\textit{ifree}_{R}(\tilde{\chi})$,
$\textup{db}_{Q^{\prime}}=\textit{ifree}_{B}(\tilde{\chi})$.

_Proof of Claim 4:_ Since $Q\in\textsl{QGLI}_{k}$ with $g_{Q}=g$ and
$S\subseteq\textup{db}_{Q}$, we have
$D_{1}\subseteq\textup{db}_{Q}\setminus\operatorname{img}(g_{Q})$. Hence
$Q_{1}=Q\langle D_{1}{\to}\bullet\rangle\in\textsl{QGLI}_{k}$. Note that
$g_{Q_{1}}=g$ and $\textup{db}_{Q_{1}}=\textup{db}_{Q}\setminus D_{1}$.

By Claim 2, $f$ is a transition for $g$; hence we have
$Q_{2}=Q_{1}[{\leadsto}f]\in\textsl{QGLI}_{k}$. Note that $g_{Q_{2}}=f\cup
g=\tilde{g}$ and
$\textup{db}_{Q_{2}}=\operatorname{img}(\tilde{g})\cup(\textup{db}_{Q}\setminus
D_{1})$. Note that $(\textup{db}_{Q}\setminus D_{1})\supseteq(S\setminus
D_{1})=D_{2}\cup D_{3}$ (by Claim 3). Hence, $\textup{db}_{Q_{2}}\supseteq
D_{2}$. Since $D_{2}=S\setminus\operatorname{img}(\tilde{g})$ we have
$D_{2}\subseteq\textup{db}_{Q_{2}}\setminus\operatorname{img}(\tilde{g})$.
Hence, $Q^{\prime}=Q_{2}\langle D_{2}{\to}\bullet\rangle\in\textsl{QGLI}_{k}$.
Note that $g_{Q^{\prime}}=\tilde{g}$ and
$\textup{dr}_{Q^{\prime}}=\textup{dr}_{Q}=\textit{ifree}_{R}(\chi)=\textit{ifree}_{R}(\tilde{\chi})$.

To complete the proof of Claim 4, we show that
$\textup{db}_{Q^{\prime}}=\textit{ifree}_{B}(\tilde{\chi})$. Note that
$\textit{ifree}_{B}(\tilde{\chi})=\operatorname{img}(\tilde{g})\cup(\textup{db}_{Q}\setminus
S)$. And $\textup{db}_{Q^{\prime}}=(\textup{db}_{Q_{2}}\setminus
D_{2})=((\operatorname{img}(\tilde{g})\cup(\textup{db}_{Q}\setminus
D_{1}))\setminus D_{2})=(\operatorname{img}(\tilde{g})\setminus
D_{2})\cup(\textup{db}_{Q}\setminus(D_{1}\cup D_{2}))$ (for the latter, recall
from Claim 3 that $D_{1}\cap D_{2}=\varnothing$). Since
$D_{2}\cap\operatorname{img}(\tilde{g})=\varnothing$ we can simplify even
further and get
$\textup{db}_{Q^{\prime}}=\operatorname{img}(\tilde{g})\cup(\textup{db}_{Q}\setminus(D_{1}\cup
D_{2}))$.

We first show that
$\textup{db}_{Q^{\prime}}\subseteq\textit{ifree}_{B}(\tilde{\chi})$: Consider
an arbitrary $j\in\textup{db}_{Q^{\prime}}$. Then, $j\not\in D_{2}$.
Furthermore, $j\in\operatorname{img}(\tilde{g})$ or
$j\in(\textup{db}_{Q}\setminus D_{1})$.

If $j\in\operatorname{img}(\tilde{g})$, then
$j\in\textit{ifree}_{B}(\tilde{\chi})$ and we are done. Otherwise,
$j\in(\textup{db}_{Q}\setminus D_{1})$. Hence, $j\not\in D_{1}\cup D_{2}$.
From Claim 3 we know that $S=D_{1}\cup D_{2}\cup D_{3}$.

In case that $j\not\in D_{3}$ we have: $j\not\in S$, and hence
$j\in(\textup{db}_{Q}\setminus S)$. Thus,
$j\in\textit{ifree}_{B}(\tilde{\chi})$.

In case that $j\in D_{3}$ we have: $j\in
D_{3}\subseteq\operatorname{img}(f)\subseteq\operatorname{img}(\tilde{g})$,
and hence $j\in\textit{ifree}_{B}(\tilde{\chi})$.

This completes the proof that
$\textup{db}_{Q^{\prime}}\subseteq\textit{ifree}_{B}(\tilde{\chi})$.

Next, we show that
$\textit{ifree}_{B}(\tilde{\chi})\subseteq\textup{db}_{Q^{\prime}}$: Consider
an arbitrary $j\in\textit{ifree}_{B}(\tilde{\chi})$. Then,
$j\in\operatorname{img}(\tilde{g})$ or $j\in(\textup{db}_{Q}\setminus S)$.
Recall from Claim 3 that $S$ is the union of the pairwise disjoint sets
$D_{1},D_{2},D_{3}$.

_Case 1:_ $j\in(\textup{db}_{Q}\setminus S)$. Then, $j\in\textup{db}_{Q}$ and
$j\not\in D_{1}\cup D_{2}\cup D_{3}$. In particular,
$j\in(\textup{db}_{Q}\setminus(D_{1}\cup
D_{2}))\subseteq\textup{db}_{Q^{\prime}}$.

_Case 2:_ $j\not\in(\textup{db}_{Q}\setminus S)$. Then,
$j\in\operatorname{img}(\tilde{g})$ and we are done since
$\operatorname{img}(\tilde{g})\subseteq\textup{db}_{Q^{\prime}}$.

This completes the proof of Claim 4. ∎${}_{\textit{Claim 4}}$

According to Claim 4, $Q^{\prime}\in\textsl{QGLI}_{k}$ and $Q^{\prime}$ has
the desired parameters
$g_{Q^{\prime}},\textup{db}_{Q^{\prime}},\textup{dr}_{Q^{\prime}}$. The next
claim ensures that $Q^{\prime}$ indeed satisfies what we aimed for in (13).

Claim 5: For every $k$-labeled incidence graph $L^{\prime}$ that satisfies the
lemma’s assumptions for $\tilde{\chi}$ we have:

$\operatorname{hom}(Q^{\prime},L^{\prime})\ =\ \textit{num}(L^{\prime}).$

Proof of Claim 5: Let $L^{\prime}$ be an arbitrary $k$-labeled incidence graph
$L^{\prime}$ that satisfies the lemma’s assumptions for $\tilde{\chi}$ (in
particular, $L^{\prime}$ has real guards w.r.t. $\tilde{g}=f\cup g$). For
$i\in[3]$ let $\ell_{i}\coloneqq|D_{i}|$. From Lemma 7.15 we obtain:
$\operatorname{hom}(Q^{\prime},L^{\prime})=\operatorname{hom}(Q_{2}\langle
D_{2}{\to}\bullet\rangle,L^{\prime})=$

$\sum_{\overline{e}_{2}\in
B(I_{L^{\prime}})^{\ell_{2}}}\operatorname{hom}(Q_{2},L^{\prime}\langle
D_{2}{\to}\overline{e}_{2}\rangle)\,.$

Furthermore, for every $\overline{e}_{2}\in B(I_{L^{\prime}})^{\ell_{2}}$ and
for $L^{\prime}_{\overline{e}_{2}}\coloneqq L^{\prime}\langle
D_{2}{\to}\overline{e}_{2}\rangle$ we have:
$\operatorname{hom}(Q_{2},L^{\prime}_{\overline{e}_{2}})=\operatorname{hom}(Q_{1}[{\leadsto}f],L^{\prime}_{\overline{e}_{2}})=$

$\operatorname{hom}(M_{f},L^{\prime}_{\overline{e}_{2}})\
\cdot\\!\\!\sum_{\overline{e}_{3}\in
B(I_{L^{\prime}})^{\ell_{3}}}\operatorname{hom}(Q_{1},L^{\prime}_{\overline{e}_{2}}\langle{X_{b}}{\to}\overline{e}_{3}\rangle)$

where
${X_{b}}\coloneqq\operatorname{img}(g_{Q_{1}})\cap\operatorname{img}(f)\cap\textup{db}_{Q_{1}}=D_{3}$
(the latter follows from Claims 3 and 4).

Since $L^{\prime}$ has real guards w.r.t. $\tilde{g}=f\cup g$, it also has
real guards w.r.t. $f$. Note that $L^{\prime}_{\overline{e}_{2}}$ differs from
$L^{\prime}$ only w.r.t. the blue labels in
$D_{2}=S\setminus\operatorname{img}(\tilde{g})$; none of these labels belongs
to $\operatorname{img}(f)$ (because
$\operatorname{img}(f)\subseteq\operatorname{img}(\tilde{g})$). Hence, also
$L^{\prime}_{\overline{e}_{2}}$ has real guards w.r.t. $f$. This implies that
$\operatorname{hom}(M_{f},L^{\prime}_{\overline{e}_{1}})=1$.

In summary, we obtain that $\operatorname{hom}(Q^{\prime},L^{\prime})=$

$\sum_{\overline{e}_{2}\in B(I_{L^{\prime}})^{\ell_{2}}}\
\sum_{\overline{e}_{3}\in
B(L^{\prime})^{\ell_{3}}}\operatorname{hom}(Q_{1},L^{\prime}_{\overline{e}_{2}}\langle
D_{3}{\to}\overline{e}_{3}\rangle)\,.$

Since $D_{2},D_{3}$ are disjoint, we obtain:
$\operatorname{hom}(Q^{\prime},L^{\prime})=$

$\sum_{\overline{e}\in B(I_{L^{\prime}})^{\ell_{2}+\ell_{3}}}\
\operatorname{hom}(Q_{1},L^{\prime}\langle(D_{2}\cup
D_{3}){\to}\overline{e}\rangle)\,.$

Recall that $Q_{1}=Q\langle D_{1}{\to}\bullet\rangle$. Hence, a further
application of Lemma 7.15 yields: $\operatorname{hom}(Q^{\prime},L^{\prime})=$

$\sum_{\overline{e}\in B(I_{L^{\prime}})^{\ell_{2}+\ell_{3}}}\ \
\sum_{\overline{e}_{1}\in
B(I_{L^{\prime}})^{\ell_{1}}}\operatorname{hom}(Q,L^{\prime}\langle(D_{2}\cup
D_{3}){\to}\overline{e}\rangle\langle D_{1}{\to}\overline{e}_{1}\rangle)\,.$

Note that $S$ is the union of the disjoint sets $D_{1},D_{2},D_{3}$ and
$\ell=|S|=\ell_{1}+\ell_{2}+\ell_{3}$. Hence,
$\operatorname{hom}(Q^{\prime},L^{\prime})=$

$\sum_{\overline{e}\in
B(I_{L^{\prime}})^{\ell}}\operatorname{hom}(Q,L^{\prime}\langle
S{\to}\overline{e}\rangle)\quad=\quad\textit{num}(L^{\prime})$

(the last equality is provided by Claim 1). Hence, the proof of Claim 5 is
complete. ∎${}_{\textit{Claim 5}}$

From Claims 4 and 5 we obtain that we have achieved (13). This completes Case
7, and it completes the proof of Lemma 8.2.∎

###  E.3 Detailed proof of Theorem 6.1

######  Proof of Theorem 6.1:.

Let $I$ and $I^{\prime}$ be arbitrary incidence graphs, and let
$k\in\mathbb{N}_{\scriptscriptstyle\geqslant 1}$. Our aim is to prove the
following:

$I\not\equiv_{\textsf{{GC}}^{{k}}}I^{\prime}\ \ \iff\ \
\textsf{{HOM}}_{\textsl{IEHW}_{k}}(I)\neq\textsf{{HOM}}_{\textsl{IEHW}_{k}}(I^{\prime})\,.\vskip
3.0pt plus 1.0pt minus 1.0pt$

Case 1: $|B(I)|\neq|B(I^{\prime})|$.
Let $J$ be the incidence graph with exactly $1$ blue node, no red node, and no
edge. Clearly, $J\in\textsl{IEHW}_{k}$. Furthermore,
$\operatorname{hom}(J,I)=|B(I)|$ and
$\operatorname{hom}(J,I^{\prime})=|B(I^{\prime})|$. As
$|B(I)|\neq|B(I^{\prime})|$, we obtain that
$\textsf{{HOM}}_{\textsl{IEHW}_{k}}(I)\neq\textsf{{HOM}}_{\textsl{IEHW}_{k}}(I^{\prime})$.

Let $m\coloneqq|B(I)|$ and consider the formula
$\psi\coloneqq\exists^{\scalebox{0.6}{$=$}m}(\texttt{{e}}_{1}).\texttt{{e}}_{1}{=}\texttt{{e}}_{1}$.
Then, $\chi\coloneqq(\top\wedge\psi)$ is a sentence in $\textsf{{GC}}^{{k}}$,
and $I\models\chi$ and $I^{\prime}\not\models\chi$. Hence,
$I\not\equiv_{\textsf{{GC}}^{{k}}}I^{\prime}$. Thus, in Case 1 we are done.

Case 2: $|B(I)|=|B(I^{\prime})|$.

For “$\Longrightarrow$” let $\chi\coloneqq(\top\wedge\psi)$ be a sentence in
$\textsf{{GC}}^{{k}}$ such that $I\models\chi$ and
$I^{\prime}\not\models\chi$. In particular, $\chi$ has the empty guard
function $g\coloneqq g_{\varnothing}$.

Let $m\coloneqq|B(I)|=|B(I^{\prime})|$, and choose an arbitrary
$d\in\mathbb{N}$ such that $d\geqslant|N_{I}(e)|$ for all $e\in B(I)$ and
$d\geqslant|N_{I^{\prime}}(e)|$ for all $e\in B(I^{\prime})$.

Let $Q\coloneqq{Q}_{\chi,m,d}\in\textsl{QGLI}_{k}$ be the $k$-labeled quantum
incidence graph provided by Lemma 8.2. Note that $Q$ has guard function
$g_{\varnothing}$, and $\textup{db}_{Q}=\textup{dr}_{Q}=\varnothing$. Let
$b_{\varnothing}$ and $r_{\varnothing}$ the labeling functions with empty
domain, and let
$L\coloneqq(I,r_{\varnothing},b_{\varnothing},g_{\varnothing})$ and
$L^{\prime}\coloneqq(I^{\prime},r_{\varnothing},b_{\varnothing},g_{\varnothing})$.
They both have real guards w.r.t. $g_{\varnothing}$ (simply because
$g_{\varnothing}$ has empty domain). From Lemma 8.2 we know that
$\operatorname{hom}(Q,L)=1$ (because $I\models\chi$) and
$\operatorname{hom}(Q,L^{\prime})=0$ (because $I^{\prime}\not\models\chi$).
Thus, $\operatorname{hom}(Q,L)\neq\operatorname{hom}(Q,L^{\prime})$. Since
$Q\in\textsl{QGLI}_{k}$, there are a degree
$\ell\in\mathbb{N}_{\scriptscriptstyle\geqslant 1}$ and coefficients
$\alpha_{1},\ldots,\alpha_{\ell}\in\mathbb{R}$ and components
$L_{1},\ldots,L_{\ell}\in\textsl{GLI}_{k}$ such that
$Q=\sum_{i=1}^{\ell}\alpha_{i}L_{i}$. We have:
$\sum_{i=1}^{\ell}\alpha_{i}\operatorname{hom}(L_{i},L)=\operatorname{hom}(Q,L)\neq\operatorname{hom}(Q,L^{\prime})=\sum_{i=1}^{\ell}\alpha_{i}\operatorname{hom}(L_{i},L^{\prime})$.
Hence there must exist an $i\in[\ell]$ with $\alpha_{i}\neq 0$ and
$\operatorname{hom}(L_{i},L)\neq\operatorname{hom}(L_{i},L^{\prime})$.

We know that $L_{i}\in\textsl{GLI}_{k}$, and $L_{i}=(I_{i},r_{i},b_{i},g_{i})$
has parameters $\textup{dr}_{Q}=\textup{db}_{Q}=\varnothing$ and guard
function $g_{i}=g_{\varnothing}$. I.e.,
$\operatorname{dom}(r_{i})=\operatorname{dom}(b_{i})=\varnothing$. From
Theorem 7.12a we know that $I_{i}\in\textsl{IEHW}_{k}$. Thus, $I_{i}$
witnesses that
$\textsf{{HOM}}_{\textsl{IEHW}_{k}}(I)\neq\textsf{{HOM}}_{\textsl{IEHW}_{k}}(I^{\prime})$.

For “$\Longleftarrow$” let $J$ be an incidence graph in $\textsl{IEHW}_{k}$
such that $\operatorname{hom}(J,I)\neq\operatorname{hom}(J,I^{\prime})$. Let
$m\coloneqq\operatorname{hom}(J,I)$. From Theorem7.12b we obtain a label-free
$\tilde{L}\in\textsl{GLI}_{k}$ such that $I_{\tilde{L}}\cong J$.

Clearly, for the label-free $k$-labeled incidence graphs $L$ and $L^{\prime}$
with $I_{L}=I$ and $I_{L^{\prime}}=I^{\prime}$ we have
$\operatorname{hom}(\tilde{L},L)=\operatorname{hom}(J,I)=m$ and
$\operatorname{hom}(\tilde{L},L^{\prime})=\operatorname{hom}(J,I^{\prime})\neq
m$.

From Lemma 8.1 we obtain a sentence $\chi\coloneqq\varphi_{\tilde{L},m}$ in
$\textsf{{GC}}^{{k}}$ such that $\mathcal{I}_{L}\models\chi$ (because
$\operatorname{hom}(\tilde{L},L)=m$) and
$\mathcal{I}_{L^{\prime}}\not\models\chi$ (because
$\operatorname{hom}(\tilde{L},L^{\prime})\neq m$). Thus, $I\models\chi$ and
$I^{\prime}\not\models\chi$. I.e., $\chi$ witnesses that
$I\not\equiv_{\textsf{{GC}}^{{k}}}I^{\prime}$.
This completes the proof of Theorem 6.1. ∎