Let $G=(V\_G,E\_G)$ and $H=(V\_H,E\_H)$ be two undirected graphs. When considering the *two-dimensional Weisfeiler-Leman* ($2$-$\mathsf{WL}$) procedure (the one corresponding to the three-variable fragment of first-order logic with counting quantifiers [[1](https://link.springer.com/article/10.1007/BF01305232)]), one typically declares $G$ and $H$ to be *distinguishable* by $2$-$\mathsf{WL}$ if the multisets of $2$-$\mathsf{WL}$ colours of pairs of vertices in $G$ and $H$ differ.


Formally, let us denote by $\chi\_{G,\mathsf{2wl}}(v,v')$ the (stable) colour of the pair $(v,v')$ of vertices in $G$, as assigned by $2$-$\mathsf{WL}$. Then, $G$ is said to be distinguishable from $H$ by $2$-$\mathsf{WL}$ if
$$
\{\!\!\{ \chi\_{G,\mathsf{2wl}}(v,v')\mid v,v'\in V\_G\}\!\!\}\neq\{\!\!\{ \chi\_{H,\mathsf{2wl}}(w,w')\mid w,w'\in V\_H\}\!\!\},
$$
where $\{\!\!\{\,\}\!\!\}$ denotes a multiset.


Consider next the following weaker notion of distinguishability: $G$ is distinguishable from $H$ by $2$-$\mathsf{WL}'$ if
$$
\{\!\!\{ \chi\_{G,\mathsf{2wl}}(v,v)\mid v\in V\_G\}\!\!\}\neq\{\!\!\{ \chi\_{H,\mathsf{2wl}}(w,w)\mid w\in V\_H\}\!\!\},
$$
where one thus only considers the $2$-$\mathsf{WL}$ colours of *vertices* (represented by pairs $(v,v)$) in the graphs.


We note that, if $G$ and $H$ are distinguishable by $2$-$\mathsf{WL}'$ then they are also distinguishable by $2$-$\mathsf{WL}$, because the $2$-$\mathsf{WL}$ colouring encodes the equality type of pairs of vertices.


**Question:** One would expect $2$-$\mathsf{WL}$ distinguishability to be stronger than $2$-$\mathsf{WL}'$ distinguishability. Is this indeed the case? That is, do there exist two graphs $G$ and $H$ (of the same number of vertices) that are distinguishable by $2$-$\mathsf{WL}$ but not by $2$-$\mathsf{WL}'$? If so, I would be interested in those graphs.


[1](https://link.springer.com/article/10.1007/BF01305232) [Jin-Yi Cai, Martin Fürer, Neil Immerman. An optimal lower bound on the number of variables for graph identification, Combinatorica, 12, 389-410, 1992.](https://link.springer.com/article/10.1007/BF01305232)



Distinguishing graphs by 2-dimensional Weisfeiler-Leman vertex colourings
These notions of distinguishability are, in fact, equivalent. If 2-WL can distinguish $G$ from $H$, then their multisets of 2-WL labels are actually disjoint. And thus, in particular, there cannot be two vertices with the same 2-WL label. See Corollary 1 in "*On the Combinatorial Power of the
Weisfeiler-Lehman Algorithm*" by Martin Fürer, where this is stated in another way: it suffices to have the same 2-WL label for two pairs of vertices, one pair in $G$, the other pair in $H$, to ensure that the entire multisets of 2-WL labels in those graphs are the same.


