# Paper claiming a graph isomorphism that isn't actually an isomorphism?

This seems like it shouldn't be a problem, but here we are.

In 'McKay’s Canonical Graph Labeling Algorithm':

on page 6, we have figure 1, a simple graph G = (V, E); V = {1,2,3,4,5,6,7,8,9), E = {(1,2), (2,3), (4,5), (5,6), (7,8), (8,9), (1,4), (2,5), (3,6), (4,7), (5,8), (6,9)}. (See link for picture. It's four squares inside a square.)

Later, on page 9, it claims that figure 3 (call it G') is an isomorphism of G. wtf? G'(E) contains (1,8), which isn't in G(E). What have I misunderstood?

Definition of a graph isomorphism:

In graph theory, an isomorphism of graphs G and H is a bijection between the vertex sets of G and H

f $\colon$ V(G) $\to$ V(H) $\,$$\!$

such that any two vertices u and v of G are adjacent in G if and only if ƒ(u) and ƒ(v) are adjacent in H.

• ... Thanks. How, exactly? f(1) and f(8) are adjacent in G', but 1 and 8 are not adjacent in G. – Zaaier Nov 1 '14 at 0:23
• And to answer your question, because I'd like to implement something. As a wise man once said, "Let he who has never had a misunderstanding about something elementary cast the first condescending comment". Or something like that. – Zaaier Nov 1 '14 at 0:54
• @Zaaier What exactly do you want to implement? Just for isomorphism testing there are many free implementations online. – Jernej Nov 1 '14 at 15:56
• @Jernej Generating the automorphism group of a graph. I could download NAutY, but then I wouldn't learn anything. – Zaaier Nov 1 '14 at 18:34

Both graphs are definitely isomorphic, since they visually have the same shape. More explicitly, one possible edge-preserving bijection $f \colon V(G) \to V(G')$ is given by: \begin{align*} f(1) &= 1 \\ f(2) &= 8 \\ f(3) &= 3 \\ f(4) &= 7 \\ f(5) &= 9 \\ f(6) &= 6 \\ f(7) &= 4 \\ f(8) &= 5 \\ f(9) &= 2 \\ \end{align*} For example, $1$ and $2$ are adjacent in $G$ and $f(1) = 1$ and $f(2) = 8$ are adjacent in $G'$.