In the famous counter example for graph isomorphism via Weisfeiler-Lehman (WL) method the following gadget was constructed in this paper by Cai, Furer and Immerman. They construct a graph $X_k = (V_k, E_k)$ given by

$V_k = A_k \cup B_k \cup M_k \\ \text{ where } \\ \quad A_k = \{a_i \mid 1 \leq i \leq k\}, \\ \quad B_k =\{b_i \mid 1 \leq i \leq k\}, \mbox{ and } \\ \quad M_k = \{ m_S \mid S \subseteq \{1,2,\ldots, k\},\ |S| \text{ is even} \}\\ E_k =\{(m_S,a_i) \mid i \in S\} \cup \{(m_S, b_i)\mid i \notin S\}$

One of the lemmas in the paper (lemma 3.1 page 6 ) states that if we color the vertices $a_i$ and $b_i$ with color $i$ then $|Aut(X_k)| = 2^{k-1}$ (color has to be preserved by the automorphism) where each automorphism corresponds to interchanging $a_i$ and $b_i$ for each $i$ in some subsets $S$ of $\{1,2,\ldots, k\}$ of even cardinality. They say that the proof is immediate. But I fail to see how even in the case of $k= 2$. In $X_2 \ (a_1, m_{\{1,2\}})$ is an edge but if we have automorphism which interchanges $a_1, b_1$ and $a_2, b_2$ the above edge gets transformed to $(b_1, m_{\{1,2\}})$ which is not an edge. So that should not be an automorphism.

I would like to understand what is my misunderstanding.


1 Answer 1


You're missing the emptyset $\emptyset$ which is connected to all $b$'s. To get an automorphism, you select a subset $T\subseteq \{1,...,k\}$ of even cardinality and then swaps $a_i$ with $b_i$ for each $i\in T$ and then adjusts the sets in the middle. In your example the graph is $$(a_1,\{12\}),(a_2,\{12\}),(b_1,\emptyset),(b_2,\emptyset).$$

Still in your example if $T=\emptyset$ you don't need to do anything and if $T=\{1,2\}$ the automorphism is given by swapping $a_1$ with $b_1$, $a_2$ with $b_2$ and $\{1,2\}$ with $\emptyset$.

Now for the general case, we need to show that there is always a way of adjusting the middle vertices. We know that $T$ has even cardinality. So let $|T|=2r$. We just need to show that such an automorphism exists if $|T|=2$ since otherwise we can apply the composition of $r$ automorphisms corresponding to partitioning $T$ into $r$ subsets of size $2$. Thus assume $T=\{i,j\}$. Then the automorphism swaps $a_i$ with $b_i$, $a_j$ with $b_j$, each middle vertex $S$ such that $S\cap\{i,j\}=\emptyset$ with the middle vertex $S\cup \{i,j\}$ (this can be seen in your example), and each subset $S$ such that $S\cap \{i,j\}=\{i\}$ with the subset such that $S\cap \{i,j\}= \{j\}$ (This you can see for $k=3$). Notice that this swapping process is an automorphism since for an index $p\neq \{i,j\}$ the edge relation between $a_p$, $b_p$ and these swapped vertices is completely preserved, and clearly the edge relation between $a_i,a_j,b_i,b_j$ is properly adjusted.

Finally to see that these are the only possible automorphisms, notice that each $a_i,b_i$ is colored with its own color. So they cannot be mapped to another pair $a_j,b_j$. Also notice that it is not possible to have an automorphism that maps an middle vertex to a middle vertex without swapping some $a_i$ with some $b_j$. $\square$

  • $\begingroup$ In general how can we show that we can always adjust the sets in the middle and get the desired automorphism? Core of my problem is actually that. $\endgroup$
    – DurgaDatta
    Commented Dec 9, 2012 at 5:32
  • $\begingroup$ Hi, I added the construction of the automorphisms. Hope it helps. $\endgroup$ Commented Dec 9, 2012 at 10:52
  • $\begingroup$ Thank you. This does not look "immediate" to me. I am very new to research. Is this a bad signal for me? $\endgroup$
    – DurgaDatta
    Commented Dec 9, 2012 at 12:53
  • $\begingroup$ "Is this a bad signal for me?" Absolutely not. I think to the contrary that your skepticism is a very good signal. Some day this kinds of things will probably be immediate for you too :) $\endgroup$ Commented Dec 9, 2012 at 13:25
  • $\begingroup$ Is it true that, for a index set $T$ (for each $i \in T$ of which are are interchanging $a_i$ and $b_i$) index set of a middle vertex $S$ get transformed to $S \Delta T$ (symmetric difference)? $\endgroup$
    – DurgaDatta
    Commented Dec 10, 2012 at 4:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.