isomorphic. The converse does not necessarily hold, as we explain next.

The CFI-graphs {#sec:CFI-graphs}
--------------

As mentioned previously, for each $k$ there is a pair of non-isomorphic graphs not distinguished by $k$-WL.

\[thm:cfi\] There is an infinite family of pairs of non-isomorphic 3-regular graphs on $\mathcal{O}(k)$ vertices not distinguished by the $k$-dimensional Weisfeiler-Leman algorithm.

=\[circle, draw\]

(a0) at (-1.5,5) ; (b0) at (-3.5,5) ;

(a2) at (1,9) ; (b2) at (-1,9) ;

(a1) at (4,5) ; (b1) at (2,5) ;

(v1) at (-3,7) ; (v2) at (-1,7) ; (v3) at (1,7) ; (v4) at (3,7) ;

(v1) edge (b0) (v1) edge (b2) (v1) edge (b1) (v2) edge (b0) (v2) edge (a2) (v2) edge (a1) (v3) edge (a0) (v3) edge (b2) (v3) edge (a1) (v4) edge (a0) (v4) edge (a2) (v4) edge (b1);

Since we intend to exploit the construction by transferring it to groups, we describe it next. We start with a connected base graph $\Gamma$. In this graph every vertex is replaced by a particular gadget and the gadgets are interconnected according to the edges of $\Gamma$ as follows. For a vertex $v$ of degree $d$ we use the gadget $F_d$, which is a graph whose vertex set consists 