Distinguishing graphs by 2-dimensional Weisfeiler-Leman vertex colourings

Question

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]), 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 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.

Answer 1

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.