Mutually Exclusive Definitions of Isomorphism?

508 Views Asked by At

Wolfram MathWorld defines Isomorphism:

Let $V(G)$ be the vertex set of a simple graph and $E(G)$ its edge set. Then a graph isomorphism from a simple graph G to a simple graph H is a bijection $f:V(G) \to V(H)$ such that $u, v \in E(G) \iff f(u), f(v) \in E(H)$.

http://mathworld.wolfram.com/GraphIsomorphism.html

Wolfram MathWorld defines Automorphism:

An automorphism of a graph is a graph isomorphism with itself, i.e., a mapping from the vertices of the given graph G back to vertices of G such that the resulting graph is isomorphic with G.

http://mathworld.wolfram.com/GraphAutomorphism.html

The page on automorphism goes on to say that the grid graph $G_{2,3}$ has four automorphisms:

Now, consider the mapping $f: V(G_{2,3}) \to V(G'_{2,3})$ given by:

$f(1) = 2,$

$f(2) = 6,$

$f(3) = 4,$

$f(4) = 3,$

$f(5) = 1,$

$f(6) = 5$

which results in:

which is consistent with the answers I got from my related post yesterday:

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

(where the most-upvoted response asked me why I'm reading math papers if I'm so ignorant)

but is inconsistent with the automorphism group of $G_{2,3}$ given by Wolfram MathWorld.

Which of the following are true:

  1. Wolfram MathWorld is using inconsistent definitions of isomorphism

  2. The people who answered my other post were using isomorphism incorrectly

  3. Stephen G. Hartke and A. J. Radcliffe are using isomorphism incorrectly

  4. I have misunderstood something here.


For context, the post I'm referring to was asking how figure 1 (page 6) and figure 3 (page 9) are isomorphic:

http://www.math.unl.edu/~aradcliffe1/Papers/Canonical.pdf

1

There are 1 best solutions below

1
On BEST ANSWER

In your previous question, we were talking about two distinct graphs with two distinct edge sets. Since both graphs visually had the same shape, it was easy to find an explicit bijection between them in order to prove that they were isomorphic.

When it comes to automorphisms, however, we are talking about a single graph and thus a single edge set. That is, we require that $G_{2,3} = G'_{2,3}$ (and not merely just $G_{2,3} \cong G'_{2,3}$). While your proposed mapping is indeed an isomorphism, it is not an automorphism because $G_{2,3} \neq G'_{2,3}$. Indeed, the original graph $G_{2,3}$ contains the edge $\{1,2\}$, yet on the other hand $\{1,2\} \notin E(G'_{2,3})$.