vertices of degree one. Furthermore, the labelled vertices in $\boldsymbol{K}$
must be connected via a path of length two with an intermediate vertex of
degree two. Hence, $\boldsymbol{K}_{2}=\boldsymbol{C}$ where $\boldsymbol{C}$
is the graph in Figure 5(b).

  2. 2.

If $\boldsymbol{K}_{1}=\boldsymbol{A}$ then the labels of $\boldsymbol{K}_{2}$
must lie on distinct vertices because $\boldsymbol{K}$ does not contain any
loops. Furthermore, the labelled vertices in $\boldsymbol{K}$ must be
adjacent. Hence, $\boldsymbol{K}_{2}$ is a graph obtained from $K_{4}$ or
$K_{2,3}$ by labelling two adjacent vertices and potentially removing the edge
between them. In any case, $\boldsymbol{C}\leq\boldsymbol{K}_{2}$.

  3. 3.

If $\boldsymbol{K}_{1}=\boldsymbol{I}$ then $\boldsymbol{K}_{2}$ is obtained
from $K_{4}$ or $K_{2,3}$ by either picking one vertex and placing both labels
on it or by adding a fresh vertex, placing a label on it, and connecting it to
a subset of the neighbours of a chosen original vertex, which receives the
other label.

  4. 4.

If $\boldsymbol{K}_{1}=\boldsymbol{J}$ then
$\boldsymbol{K}_{2}=\boldsymbol{K}$. In particular, $\boldsymbol{K}_{2}$ is
obtained from $K_{4}$ or $K_{2,3}$ by the procedure described in Item 3.

  5. 5.

$\boldsymbol{K}_{1}$ cannot be any of the two remaining bilabelled minors of
$\boldsymbol{P}$ since these contain an unlabelled vertex of degree at most
one which is not the case for $\boldsymbol{K}$.

If
$\boldsymbol{C}\leq\boldsymbol{F}=\boldsymbol{F}_{1}\cdot\boldsymbol{F}_{2}$
then, by Lemma D.19, $\boldsymbol{C}\leq\boldsymbol{F}_{1}$ or
$\boldsymbol{C}\leq\boldsymbol{F}_{2}$ because the graph $\boldsymbol{C}$
cannot be written as the series composition of two graphs different from
$\boldsymbol{I}$. The bilabelled minor $\boldsymbol{C}$ of
$\boldsymbol{F}_{1}$ or $\boldsymbol{F}_{2}$ gives rise to a $K_{2,3}$-minor
in their expansion, contradicting that
$\boldsymbol{F}_{1},\boldsymbol{F}_{2}\in\mathcal{OP}$.

It remains to consider the case in Items 3 and 4. Let $\boldsymbol{K}_{2}$ be
the graph described there. This graph can only be written as the series
composition of two graphs different from $\boldsymbol{I}$ if the two labels do
not coincide. In this case, one of the labelled vertices is adjacent to a
subset of neighbours of the other labelled vertex. The graph
$\boldsymbol{K}_{2}$ may be written as series composition of $\boldsymbol{A}$
or $\boldsymbol{J}$ with another graph $\boldsymbol{K}^{\prime}_{2}$. The
graph $\operatorname{soe}(\boldsymbol{K}^{\prime}_{2})$ contains $K_{4}$ or
$K_{2,3}$ as a minor. By Lemma D.13, one of the factors $\boldsymbol{F}_{1}$
or $\boldsymbol{F}_{2}$ is not outerplanar, a contradiction.

For a vertex $u$ of a graph $F$ write $N_{F}(u)\coloneqq\\{v\in V(F)\mid uv\in
E(F)\\}$ for the set of neighbours of $u$.

######  Lemma D.27.

Let $F$ be an outerplanar graph with vertex $u\in V(F)$. If $u$ is not
isolated then there exists a neighbour $v\in N_{F}(u)$ such that the graph
obtained from $F$ by subdividing the edge $uv$ is outerplanar.

######  Proof D.28.

Take an outerplanar embedding of $F$ which has some face incident to all the
vertices and then consider some edge incident to $u$ that is incident to this
face and then subdivide that edge. Clearly the embedding remains outerplanar
when the edge is subdivided. Alternatively, one may consider the following
argument:

If $u$ is of degree one or two, any of its neighbours is as desired. If $u$
has degree at least three, observe that $F[N_{F}(u)]$ cannot contain $K_{3}$
as a minor. Indeed, any such minor would give rise to a $K_{4}$-minor in $F$.
Hence, $F[N_{F}(u)]$ is a forest and contains a vertex $v$ of degree at most
one in $F[N_{F}(u)]$. Write $F^{\prime}$ for the graph obtained from $F$ by
subdividing the edge $uv$. Write $w$ for the vertex added this way.

If $F^{\prime}$ is not outerplanar then it contains a minor $K_{4}$ or
$K_{2,3}$ which can be obtained from $F^{\prime}$ without undoing the
subdivision. This minor cannot be $K_{4}$ because $w$ is of degree two. Hence,
$F^{\prime}$ contains a $K_{2,3}$-minor which can be obtained from $F$ such
that the path $uwv$ is not contracted. This implies that $v$ is adjacent to at
least two neighbours of $u$ which cannot be since it was chosen to be of
degree one in $F[N_{F}(u)]$, a contraction. The graph $F^{\prime}$ is
outerplanar.

######  Lemma D.29.

Let $\boldsymbol{F}=(F,u,v)\in\mathcal{OP}$ have $n\geq 3$ vertices.

  1. 1.

If $u=v$ then
$\boldsymbol{F}=\boldsymbol{I}\odot(\boldsymbol{K}\cdot\boldsymbol{J})$ or
$\boldsymbol{F}=\boldsymbol{I}\odot((\boldsymbol{A}\odot\boldsymbol{K})\cdot\boldsymbol{J})$
where $\boldsymbol{K}=(K,x,y)\in\mathcal{OP}$ has at most $n$ vertices and
$x\neq y$.

  2. 2.

If $uv\in E(F)$ then $\boldsymbol{F}=\boldsymbol{A}\odot\boldsymbol{K}$ where
$\boldsymbol{K}=(K,x,y)\in\mathcal{OP}$ has at most $n$ vertices and satisfies
$x\neq y$ and $xy\not\in E(K)$,

  3. 3.

If $u\neq v$ and $uv\not\in E(F)$ then
$\boldsymbol{F}=\boldsymbol{K}\cdot\boldsymbol{L}$ where
$\boldsymbol{K},\boldsymbol{L}\in\mathcal{OP}$ have at least $2$ and at most
$n-1$ vertices.

######  Proof D.30.

For Item 1, distinguishing two cases: if $u=v$ is isolated in $F$ then let
$x\in V(F)\setminus\\{u\\}$ be arbitrary. Define $K\coloneqq F$. Then
$\boldsymbol{K}\coloneqq(K,u,x)$ is such that
$\boldsymbol{F}=\boldsymbol{I}\odot(\boldsymbol{K}\cdot\boldsymbol{J})$. By
definition, $K$ is outerplanar. Noting that $u$ is isolated, it is easy to see
that the expansion of $\boldsymbol{K}$ is outerplanar as well. If $u=v$ is not
isolated, pick a neighbour $x$ in virtue of Lemma D.27, and let $K$ be the
graph obtained from $F$ by deleting the edge $ux$, i.e. $V(K)\coloneqq V(F)$
and $E(K)\coloneqq E(F)\setminus\\{ux\\}$. Let
$\boldsymbol{K}\coloneqq(K,u,x)$. Clearly, $K$ is outerplanar. The expansion
of $\boldsymbol{K}$ is the graph obtained from $F$ by subdividing the edge
$ux$ and outerplanar by Lemma D.27. Hence, $\boldsymbol{K}\in\mathcal{OP}$.
Furthermore,
$\boldsymbol{F}=\boldsymbol{I}\odot((\boldsymbol{A}\odot\boldsymbol{K})\cdot\boldsymbol{J})$.

For Item 2, define $K$ by removing the edge $uv$ from $F$, i.e. $V(K)\coloneqq
V(F)$ and $E(K)\coloneqq E(F)\setminus\\{uv\\}$. The graph
$\boldsymbol{K}\coloneqq(K,u,v)$ satisfies
$\boldsymbol{F}=\boldsymbol{A}\odot\boldsymbol{K}$ and all other stipulated
properties.

For Item 3, first suppose that $u$ and $v$ lie in the same connected component
of $F$. Observe that there no two internally vertex-disjoint paths from $u$ to
$v$ since a pair of two such paths would give rise to a $K_{2,3}$-minor in the
expansion of $\boldsymbol{F}$. By Menger’s Theorem, there exists a vertex
$x\neq u,v$ meeting all paths from $u$ to $v$. Thus, removing $x$ from $F$
causes $u$ and $v$ to lie in separate connected components. Let $A$ denote the
connected component of $F-x$ containing $u$, $B$ the connected component of
$F-x$ containing $v$, and $C$ the union of all connected components of $F-x$
containing neither $u$ nor $v$. Clearly, $V(F)=A\sqcup B\sqcup
C\sqcup\\{x\\}$. Define $K\coloneqq F[A\cup\\{x\\}]$ as the subgraph of $F$
induced by $A\cup\\{x\\}$ and similarly $L\coloneqq F[B\cup C\cup\\{x\\}]$.
Let $\boldsymbol{K}\coloneqq(K,u,x)$ and $\boldsymbol{L}\coloneqq(L,x,v)$.
Then $\boldsymbol{F}=\boldsymbol{K}\cdot\boldsymbol{L}$, as desired. As they
are induced subgraphs of $F$, the graphs $K$ and $L$ are outerplanar. The
expansions of $\boldsymbol{K}$ and $\boldsymbol{L}$ are minors of the
expansion of $\boldsymbol{F}$ and thus outerplanar. Observe that
$|V(K)|+|V(L)|=n+1$ and $|V(K)|,|V(L)|\geq 2$, as desired.

Now suppose that $u$ and $v$ lie in separate connected components of $F$. Let
$A$ denote the connected component of $F$ containing $u$, $B$ the connected
component of $F$ containing $v$, and $C$ the union of all connected components
of $F$ containing neither $u$ nor $v$. Observe that $|A|+|B|+|C|=n\geq 3$.
Distinguish cases:

  * •

If $|A|+|C|\geq 2$, let $K\coloneqq F[A\cup C]$ and $L^{\prime}\coloneqq
F[B]$. Define $\boldsymbol{K}\coloneqq(K,u,u)$,
$\boldsymbol{L}^{\prime}\coloneqq(L^{\prime},v,v)$, and
$\boldsymbol{L}\coloneqq\boldsymbol{J}\cdot\boldsymbol{L}^{\prime}$.

  * •

Otherwise, it holds that $|B|\geq 2$. Let $K^{\prime}\coloneqq F[A\cup B]$ and
$L\coloneqq F[B]$. Define $\boldsymbol{K}^{\prime}\coloneqq(K^{\prime},u,u)$,
$\boldsymbol{L}\coloneqq(L,v,v)$, and
$\boldsymbol{K}\coloneqq\boldsymbol{K}^{\prime}\cdot\boldsymbol{J}$.

In both cases, $\boldsymbol{F}=\boldsymbol{K}\cdot\boldsymbol{L}$ and
$\boldsymbol{K},\boldsymbol{L}\in\mathcal{OP}$. Furthermore, writing $K$ and
$L$ for the graphs underlying $\boldsymbol{K}$ and $\boldsymbol{L}$
respectively, it holds that $|V(K)|+|V(L)|=n+1$ and $|V(K)|,|V(L)|\geq 2$
since multiplication with $\boldsymbol{J}$ amounts to adding a fresh isolated
vertex.

The following Corollary D.31 implies Proposition 4.16.

######  Corollary D.31.

The classes $\mathcal{L}_{1}$ and $\mathcal{OP}$ coincide.

######  Proof D.32.

For the inclusion $\mathcal{L}_{1}\subseteq\mathcal{OP}$, observe that the the
atomic graphs in $\mathcal{A}_{1}$ are
$\boldsymbol{A},\boldsymbol{J},\boldsymbol{I}\in\mathcal{OP}$. By Lemma D.25,
$\mathcal{OP}$ is closed under series composition, parallel composition with
atomic graphs, and permutation of labels. It follows inductively that
$\mathcal{L}_{1}\subseteq\mathcal{OP}$.

For the inclusion $\mathcal{L}_{1}\supseteq\mathcal{OP}$, it is argued that
$\boldsymbol{F}\in\mathcal{L}_{1}$ if $\boldsymbol{F}\in\mathcal{OP}$ by
induction on the number of vertices in $\boldsymbol{F}$. If $\boldsymbol{F}$
has at most two vertices, this is clear. Suppose $\boldsymbol{F}=(F,u,v)$ has
$n\geq 3$ vertices. By Items 1 and 2 of Lemma D.29, it may be supposed that
$u\neq v$ and $uv\not\in E(F)$. In this case, again by Lemma D.29,
$\boldsymbol{F}=\boldsymbol{K}\cdot\boldsymbol{L}$ for graphs $\boldsymbol{K}$
and $\boldsymbol{L}$, to which the inductive hypothesis applies. It follows
that $\boldsymbol{F}\in\mathcal{L}_{1}$.

##  Appendix E Material Omitted in Section 5

######  Theorem E.1.

Let $t\geq 1$. For graphs $G$ and $H$ with $\boldsymbol{r},\boldsymbol{s}\in
V(G)^{t}$ and $\boldsymbol{u},\boldsymbol{v}\in V(H)^{t}$, the following are
equivalent:

  1. 1.

$\mathsf{mwl}_{G}^{\infty}(\boldsymbol{r},\boldsymbol{s})=\mathsf{mwl}_{H}^{\infty}(\boldsymbol{u},\boldsymbol{v})$,

  2. 2.

for all $\boldsymbol{F}\in\mathcal{L}_{t}^{+}$,
$\boldsymbol{F}_{G}(\boldsymbol{r},\boldsymbol{s})=\boldsymbol{F}_{H}(\boldsymbol{u},\boldsymbol{v})$,

  3. 3.

for all $\varphi\in\mathsf{M}^{t}$ with $2t$ free variables,
$G\models\varphi(\boldsymbol{r},\boldsymbol{s})$ if and only if
$H\models\varphi(\boldsymbol{u},\boldsymbol{v})$.

The proof of Theorem E.1 is based on the following lemma, which is adopted
from [14, Lemma 6]. An _$\mathcal{L}_{t}^{+}$ -quantum graph_ is a finite
linear combination $q=\sum\alpha_{i}\boldsymbol{F}^{i}$ of graphs
$\boldsymbol{F}^{i}\in\mathcal{L}_{t}^{+}$. Operations like series or parallel
composition can be extended linearly to quantum graphs. Write $q_{G}$ for the
linear combination $\sum\alpha_{i}\boldsymbol{F}^{i}_{G}$ of homomorphism
tensors.

######  Lemma E.2.

Let $t\geq 1$ and $n\in\mathbb{N}$. For every $\varphi\in\mathsf{M}^{t}$ with
$2t$ free variables, there exists an $\mathcal{L}_{t}^{+}$-quantum graph $q$
such that for all graphs $G$ on $n$ vertices it holds that

  * •

if $G\models\varphi(\boldsymbol{r}\boldsymbol{s})$ then
$t_{G}(\boldsymbol{r}\boldsymbol{s})=1$, and

  * •

if $G\not\models\varphi(\boldsymbol{r}\boldsymbol{s})$ then
$t_{G}(\boldsymbol{r}\boldsymbol{s})=0$.

######  Proof E.3.

If $\varphi$ is a quantifier-free formula then there exists an atomic graph
$\boldsymbol{F}\in\mathcal{A}_{t}$ such that
$G\models\varphi(\boldsymbol{r},\boldsymbol{s})$ if and only if
$\boldsymbol{F}_{G}(\boldsymbol{r},\boldsymbol{s})=1$. Furthermore, the
homomorphism tensor of any atomic graph has entries from $\\{0,1\\}$.

If $\varphi$ is of the form $\neg\psi$, let $q$ denote
$\mathcal{L}_{t}^{+}$-quantum graph constructed inductively for $\psi$. Then
$r\coloneqq\boldsymbol{J}-q$ for $\boldsymbol{J}$ as defined in Definition 3.5
is an $\mathcal{L}_{t}^{+}$-quantum graph as desired.

If $\varphi$ is of the form $\psi\land\chi$, let $q$ and $r$ denote
$\mathcal{L}_{t}^{+}$-quantum graphs constructed inductively for $\psi$ and
$\chi$, respectively. Then $s\coloneqq q\odot r$ is an
$\mathcal{L}_{t}^{+}$-quantum graph as desired.

If $\varphi$ is of the form $\psi\lor\chi$, it is equivalent to
$\neg(\neg\psi\land\neg\chi)$ and the two previous cases can be applied
jointly.

It remains to consider the case in which $\varphi$ is of the form
$\exists^{\geq\ell}\boldsymbol{y}.\
\psi(\boldsymbol{x},\boldsymbol{y})\land\chi(\boldsymbol{y},\boldsymbol{z})$.
Let $q$ and $r$ denote the $\mathcal{L}_{t}^{+}$-quantum graphs constructed
inductively for $\psi$ and $\chi$, respectively. Then $(q\cdot
r)_{G}(\boldsymbol{r},\boldsymbol{s})=\sum_{\boldsymbol{t}\in
V(G)^{t}}q_{G}(\boldsymbol{r},\boldsymbol{t})r_{G}(\boldsymbol{t},\boldsymbol{s})$
equals the number of elements $\boldsymbol{t}\in V(G)^{t}$ such that
$G\models\psi(\boldsymbol{r},\boldsymbol{t})\land\chi(\boldsymbol{t},\boldsymbol{s})$.
Let $P=\sum c_{i}x^{i}$ be a polynomial such that
$P(0)=P(1)=\dots=P(\ell-1)=0$ and $P(\ell)=P(\ell+1)=\dots=P(n^{t})=1$. Then
the quantum graph $P(q\cdot r)=\sum c_{i}(q\cdot r)^{\odot i}$ where $(q\cdot
r)^{\odot i}$ denotes the parallel composition of $i$ copies of $q\cdot r$ is
as desired.

######  Proof E.4 (Proof of Theorem E.1).

Supposing Item 1, Item 2 is proven by induction on the structure of
$\boldsymbol{F}$. If $\boldsymbol{F}$ is atomic then the statement follows
from
$\operatorname{rel}_{G}(\boldsymbol{r},\boldsymbol{s})=\operatorname{rel}_{H}(\boldsymbol{u},\boldsymbol{v})$.
For $\boldsymbol{F}=\boldsymbol{K}\odot\boldsymbol{L}$ and
$\boldsymbol{F}=\boldsymbol{K}^{\sigma}$ with
$\boldsymbol{K},\boldsymbol{L}\in\mathcal{L}_{t}^{+}$, the statement is easily
verified. It remains to consider the case
$\boldsymbol{F}=\boldsymbol{K}\cdot\boldsymbol{L}$. By definition of
$\mathsf{mwl}$, there exists a bijection $\pi\colon V(G)^{t}\to V(H)^{t}$ such
that

$\mathsf{mwl}_{G}^{\infty}(\boldsymbol{r},\boldsymbol{t})=\mathsf{mwl}_{H}^{\infty}(\boldsymbol{u},\pi(\boldsymbol{t}))\quad\text{and}\quad\mathsf{mwl}_{G}^{\infty}(\boldsymbol{t},\boldsymbol{s})=\mathsf{mwl}_{H}^{\infty}(\pi(\boldsymbol{t}),\boldsymbol{v})$

for all $\boldsymbol{t}\in V(G)^{t}$. Hence,

$\boldsymbol{F}_{G}(\boldsymbol{r},\boldsymbol{s})=\sum_{\boldsymbol{t}\in
V(G)^{t}}\boldsymbol{K}_{G}(\boldsymbol{r},\boldsymbol{t})\boldsymbol{L}_{G}(\boldsymbol{t},\boldsymbol{s})=\sum_{\boldsymbol{t}\in
V(G)^{t}}\boldsymbol{K}_{H}(\boldsymbol{u},\pi(\boldsymbol{t}))\boldsymbol{L}_{H}(\pi(\boldsymbol{t}),\boldsymbol{v})=\boldsymbol{F}_{H}(\boldsymbol{u},\boldsymbol{v}).$

Hence, Item 2 holds.

Now suppose that Item 2 holds. It is easy to see that $G$ and $H$ must have
the same number of vertices. If $\varphi\in\mathsf{M}^{t}$ with $2t$ free
variables is such that $G\models\varphi(\boldsymbol{r},\boldsymbol{s})$ and
$H\not\models\varphi(\boldsymbol{u},\boldsymbol{v})$ then, by Lemma E.2, there
exits a graph $\boldsymbol{F}\in\mathcal{L}_{t}^{+}$ such that
$\boldsymbol{F}_{G}(\boldsymbol{r},\boldsymbol{s})\neq\boldsymbol{F}_{H}(\boldsymbol{u},\boldsymbol{v})$.
This yields Item 3.

That Item 3 implies Item 1 is proven similarly as [7, Theorem 5.2] by
induction on the number of iterations. Clearly,
$\mathsf{mwl}_{G}^{0}(\boldsymbol{r},\boldsymbol{s})=\mathsf{mwl}_{H}^{0}(\boldsymbol{u},\boldsymbol{v})$.

Since $\mathsf{M}^{t}$ is closed under permuting the names of the variables,
it holds for all $\sigma\in\mathfrak{S}_{2t}$ that
$G\models\varphi(\boldsymbol{r}\boldsymbol{s})\iff
H\models\varphi(\boldsymbol{u}\boldsymbol{v})$ for all
$\varphi\in\mathsf{M}^{t}$ with $2t$ free variables if and only if
$G\models\varphi(\sigma(\boldsymbol{r}\boldsymbol{s}))\iff
H\models\varphi(\sigma(\boldsymbol{u}\boldsymbol{v}))$ for all
$\varphi\in\mathsf{M}^{t}$ with $2t$ free variables. Hence, if
$\mathsf{mwl}_{G}^{i}(\boldsymbol{r}\boldsymbol{s})=\mathsf{mwl}_{H}^{i}(\boldsymbol{u}\boldsymbol{v})$
for some $i\in\mathbb{N}$ then also
$\mathsf{mwl}_{G}^{i+1/2}(\boldsymbol{r}\boldsymbol{s})=\mathsf{mwl}_{H}^{i+1/2}(\boldsymbol{u}\boldsymbol{v})$.

For the step from $i+1/2$ to $i+1$, suppose contrapositively that
$\mathsf{mwl}_{G}^{i+1}(\boldsymbol{r}\boldsymbol{s})\neq\mathsf{mwl}_{H}^{i+1}(\boldsymbol{u}\boldsymbol{v})$.
By the previous argument, it can be supposed that
$\mathsf{mwl}_{G}^{i+1/2}(\boldsymbol{r}\boldsymbol{s})=\mathsf{mwl}_{H}^{i+1/2}(\boldsymbol{u}\boldsymbol{v})$.
Hence, there exists a pair of colours
$\left(\mathsf{mwl}_{G}^{i+1/2}(\boldsymbol{r}\boldsymbol{t}),\mathsf{mwl}_{G}^{i+1/2}(\boldsymbol{t}\boldsymbol{s})\right)$
which appears in the multisets for $G$ and $H$ differently often. By the
inductive hypothesis, for each pair of distinct $\mathsf{mwl}^{i+1/2}$-colours
there exists a formula $\varphi\in\mathsf{M}^{t}$ with $2t$ free variables
which is satisfied by all vertex tuples of the first colour and by none of the
second colour. By taking the conjunction of several such formulae, a formula
can be constructed which holds for a $2t$-tuple of vertices of $G$ or $H$ if
and only if they have a specified colour in $\mathsf{mwl}^{i+1/2}$. Let
$\varphi$ and $\psi$ be formulae which hold exactly for the $2t$-tuples of
vertices of $G$ or $H$ of colours
$\mathsf{mwl}_{G}^{i+1/2}(\boldsymbol{r}\boldsymbol{t})$ and
$\mathsf{mwl}_{G}^{i+1/2}(\boldsymbol{t}\boldsymbol{s})$, respectively. By
assumption, there is an $N\in\mathbb{N}$ such that the formula
$\Phi\coloneqq\exists^{\geq N}\boldsymbol{y}.\
\varphi(\boldsymbol{x},\boldsymbol{y})\land\psi(\boldsymbol{y},\boldsymbol{z})\in\mathsf{M}^{t}$
is such that $G\models\Phi(\boldsymbol{r}\boldsymbol{s})$ and
$H\not\models\Phi(\boldsymbol{u}\boldsymbol{v})$. This yields Item 1.

######  Proof E.5 (Proof of Theorem 5.3).

Supposing Item 1, let $\pi\colon V(G)^{2t}\to V(H)^{2t}$ be a bijection such
that
$\mathsf{mwl}_{G}^{\infty}(\boldsymbol{rs})=\mathsf{mwl}_{H}^{\infty}(\pi(\boldsymbol{rs}))$
for all $\boldsymbol{r},\boldsymbol{s}\in V(G)^{t}$. By Theorem E.1, for
$\boldsymbol{F}=(F,\boldsymbol{u},\boldsymbol{v})\in\mathcal{L}_{t}^{+}$,

$\hom(F,G)=\sum_{\boldsymbol{r},\boldsymbol{s}\in
V(G)^{t}}\boldsymbol{F}_{G}(\boldsymbol{r},\boldsymbol{s})=\sum_{\boldsymbol{r},\boldsymbol{s}\in
V(G)^{t}}\boldsymbol{F}_{H}(\pi(\boldsymbol{rs}))=\hom(F,H),$

so Item 2 holds.

Assuming Item 2 holds, let $\varphi$ be an $\mathsf{M}^{t}$-sentence. Consider
the $\mathsf{M}^{t}$-formula
$\psi\coloneqq\varphi\land(x_{1}=x_{1})\land\dots\land(x_{2t}=x_{2t})$ with
$2t$ free variables. Clearly, $G\models\varphi$ if and only if
$G\models\psi(\boldsymbol{rs})$ for any $\boldsymbol{r},\boldsymbol{s}\in
V(G)^{t}$. Let $q$ denote the $\mathcal{L}_{t}^{+}$-quantum graph constructed
for $\psi$ via Lemma E.2. Then Item 2 implies that
$q_{G}(\boldsymbol{r},\boldsymbol{s})=q_{H}(\boldsymbol{u},\boldsymbol{v})$
for all $\boldsymbol{r},\boldsymbol{s}\in V(G)^{t}$ and
$\boldsymbol{u},\boldsymbol{v}\in V(H)^{t}$. Hence, $G\models\varphi$ if and
only if $H\models\varphi$. This yields Item 3.

Assuming Item 3 holds, suppose that $G$ and $H$ are distinguished by the
$\mathsf{mwl}$ algorithm and let $C\subseteq V(G)^{2t}$ denote a
$\mathsf{mwl}$-colour class in $G$ whose counterpart $D\subseteq V(G)^{2t}$
has a different size in $H$. For a tuples $\boldsymbol{r}\in V(G)^{t}$, write
$s(\boldsymbol{r})\coloneqq|\\{\boldsymbol{s}\in
V(G)^{t}\mid\boldsymbol{rs}\in C\\}|$. For $\boldsymbol{u}\in V(H)^{t}$, write
$s(\boldsymbol{u})\coloneqq|\\{\boldsymbol{v}\in
V(H)^{t}\mid\boldsymbol{uv}\in D\\}|$. Since $|C|\neq|D|$, also
$\left\\{\\!\\!\left\\{s(\boldsymbol{r})\mid\boldsymbol{r}\in
V(G)^{t}\right\\}\\!\\!\right\\}\neq\left\\{\\!\\!\left\\{s(\boldsymbol{u})\mid\boldsymbol{u}\in
V(H)^{t}\right\\}\\!\\!\right\\}$. By Theorem E.1, there exists a formula
$\varphi\in\mathsf{M}^{t}$ with $2t$ free variables which is only satisfied by
tuples in $C$ and $D$ and by no other tuples. The $\mathsf{M}^{t}$-sentence
$\exists^{\geq N_{1}}\boldsymbol{x}.\ \left(\exists^{\geq
N_{2}}\boldsymbol{y}.\
\left(\varphi(\boldsymbol{x},\boldsymbol{y})\land\top\right)\right)\land\top$
is not satisfied by both $G$ and $H$ for some $N_{1},N_{2}\in\mathbb{N}$.