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.

  • $\begingroup$ ... Thanks. How, exactly? f(1) and f(8) are adjacent in G', but 1 and 8 are not adjacent in G. $\endgroup$ – Zaaier Nov 1 '14 at 0:23
  • 1
    $\begingroup$ 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. $\endgroup$ – Zaaier Nov 1 '14 at 0:54
  • $\begingroup$ @Zaaier What exactly do you want to implement? Just for isomorphism testing there are many free implementations online. $\endgroup$ – Jernej Nov 1 '14 at 15:56
  • $\begingroup$ @Jernej Generating the automorphism group of a graph. I could download NAutY, but then I wouldn't learn anything. $\endgroup$ – 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'$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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