# counterexample for this graph isomorphism algorithm

I'm trying to learn about graph isomorphism and I stumbled upon coloring. When given 2 graphs, you give each vertex a color according to properties of their neighbors and any vertex on graph 1 can only map to any vertex on graph 2 with the same color. This way you cannot have false negatives (if the algorithm says there's no mapping, it is so) but you may have false positives. So now I'm looking for a false positive of my particular graph isomorphism coloring algorithm.

We're going to assign each vertex a "breadth" and a "color", which are both strings. Assume both graphs have n vertices.

Step 1: we assign depth=0. We pick a starting vertex and assign it
(breadth, color) = ("0;","0;").
We assign a set S={that vertex}.

Step 2: depth++;
set T=[all neighbors that don't have a color yet of all vertices in S].

Step 2.A: for each vertex in T, name it t and set t.breadth = depth + ";"

Step 2.B: for each t in T:
t.breadth += '[' + (concatenate all colors of all
neighbours of t that are in S, in lexicographically sorted order) + '];'

Step 2.C: for each t in T:
t.color = t.breadth + '{'+(all breadths of all neighbours
of t that are in T, concatenated in lexicographically sorted order)+'}'

Step 2.D: S=T; goto step 2 unless T is empty.

Step 3: Save the resulting coloring, clear S and T and the coloring and
repeat from step 1 for *each possible starting vertex for both graphs*.

Step 4: We now have n colorings for both graphs. Deduce if this leads to a
negative. If not, for now assume that the graphs are isomorphic.


A bit of explanation on step 4: Suppose I pick a starting vertex for graph 1, we need to look at each starting vertex for graph 2. If a starting vertex for graph 2 then leads the exact same number of colors for each color of graph 1, we have possible vertex mappings from graph 1 to graph 2. If this is also the case for another starting vertex of graph 2, we have extra mapping possibilities. with 1 starting vertex for graph 1, we look at all starting vertices from graph 2 and union the results together.

When looking at another starting vertex for graph 1, we get another set of mappings. Each starting vertex of graph 1 leads to a set of mappings, and we're looking at the interesection of those sets. If that intersection is empty, the graphs are not isomorphic.

Now, I'm looking for two graphs for which this algorithm says they're isomorphic, while they're not.

I'm assuming that the graphs are connected.

Note that the colors might grow exponentially large this way, but we can avoid that by replacing parts with placeholders.

There are two non-isomorphic graphs with 16 vertices in which each vertex has 6 neighbors and 9 vertices at distance 2: the Shrikhande graph and the $4\times 4$ rook's graph.