Consider the simple path graph, $P$ over vertices labeled from $1$ to $n$. If all path graphs over $n$ vertices are isomorphic to $P$ (I can relabel the vertices in $n!$ ways and still have the same graph.), then why does $P$ have only 2 automorphisms?

Edit: Is the explanation related the fact that there is only one vertex set to map vertices from?


While you can label the vertices of a path graph in $n!$ different ways, most of of these labelings do not correspond to isomorphisms between the graphs. For example, if the vertex labelled by $1$ in the first graph were one an end of the path but was not on the end in the second graph, any map that sent vertex $1$ in the first graph to vertex $1$ in the second graph would not be an isomorphism since isomorphisms cannot map a vertex in the first graph to a vertex in the second graph that has a different degree. So from your $n!$ ways of labeling the graphs, you obtain $n!$ graphs which are all isomorphic, but there are just two isomorphisms between any given pair of these graphs.

In fact, the number of isomorphisms between two isomorphic graphs is always equal to the number of automorphisms of one of the graphs. This is because if $X$ and $Y$ are graphs, $\mathrm{Aut}(X)$ is the automorphism group of $X$ and $\phi : X \rightarrow Y$ is an isomorphism, then the coset of all isomorphisms from $X$ to $Y$ is $\phi \circ \mathrm{Aut}(X) = \{\phi \circ \sigma \vert \sigma \in \mathrm{Aut}(X)\}$. Clearly, this set has the same cardinality as $\mathrm{Aut}(X)$. (Actually, this last paragraph holds not just for graphs but for just about any mathematical object you can imagine.)

To answer the question in your edit, this does not depend on whether the two graphs have the same vertex set.

  • $\begingroup$ I see now that it follows from the definition that an isomorphism does not map vertices having different degrees. But then how does isomorphism encapsulate the notion of 'sameness' of two graphs(i.e. "Is graph $A$ superimposable on a graph $B$(nevermind the vertex labels)?")? $\endgroup$ – Akay Feb 16 '17 at 9:53
  • $\begingroup$ @Akay An isomorphism is a bijection that such that there is an edge between a pair of vertices in the first graph if and only if there is an edge between their images in the second graph. Thus, you can see that the definition states exactly that they must have the same edge structure with possibly different vertex labels. $\endgroup$ – Qudit Feb 16 '17 at 9:57
  • $\begingroup$ I'm pretty new to graph theory - I got started on discrete math a few months ago. Anyways, I think I see it now! The defining characteristic of a vertex is its position in the graph structure. Relabelling a vertex does not change this basic fact, since what makes a vertex unique is the edges around it. So, all that an automorphism does is shuffle around the 'invariant'/'equivalent' vertices. Do I understand it correctly? $\endgroup$ – Akay Feb 16 '17 at 13:55
  • $\begingroup$ @Akay What is important for isomorphism is the position of each vertex relative to other vertices. We could erase all the labels of the vertices in a drawing of a graph and not lose any information about its isomorphism class. $\endgroup$ – Qudit Feb 16 '17 at 16:42

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.