# Graph isomorphism and existence of nontrivial automorphisms

Consider the following two algorithmic problems - one of determining whether two graphs are isomorphic and the other of determining if a graph has a nontrivial automorphism:

(1) Decision problem: Graph isomorphism. Instance: Graphs $G$ and $H$. Question: Is $G \cong H$?

(2) Decision problem: Nontrivial automorphism group. Instance: A graph $G$. Question: Is $Aut(G)>1$.

An article I'm reading ([P. J. Cameron, "Automorphisms of graphs,'' Chapter 5, Topics in Algebraic Graph Theory]) says that if we can solve (1), then we can solve (2) "by attaching distinctive `gadgets' at each vertex and checking whether any pair of the resulting graphs are isomorphic.''

For example, if $G$ is the 4-cycle graph on vertices $a,b,c,d$, then, we can attach the cycle graphs $C_5, C_6, C_7, C_8$ to $a,b,c,d$, respectively, to get a graph $G'$. We can attach $C_7, C_6, C_5, C_8$, to $a,b,c,d$, respectively, to get a graph $G''$. If $G' \cong G''$, then $(a,c)$ is an automorphism of $G$.

It seems to me that to solve (2) the number of pairs to check for isomorphism is superexponential and on the order of $n!$ at first thought, where $n$ is the number of vertices of $G$. Is it true that (2) does not have the same complexity as (1), at least given just this proof of attaching gadgets?

Take an "appropriate" gadget $X$ and for a vertex $v \in V(G)$, let $H_v$ be the graph you obtain by attaching $X$ at $v$.
A nontrivial automorphism of $G$ exists if and only if there are $u, v \in V(G)$ and $v \ne u$ with $H_v \cong H_u$. You need only run the isomorphism algorithm at most $O(|V(G)|^2)$ times to get your answer.
• I agree with the "if" part of your statement but do not see why the "only if" should be true. It seems to me a nontrivial automorphism of $G$ can't be detected by your method of $|V|-1$ isomorphism tests if that initial vertex $v$ is an orbit of length 1 (under the action of $Aut(G)$ on $V(G)$). For example, take $G$ to be the path graph with edge set $\{12, 23, 34, 45, 46\}$ that has a unique nontrivial automorphism $(5,6)$, and take $v=1$. Attach some gadget $X$ to vertex v to obtain $H$. Then, $H_u$ will be nonisomorphic to $H$, for every $u \ne v$, but $Aut(G)>1$. – AG. Dec 14 '13 at 2:39
• Yes, the permutation $(u,v,\ldots)\cdots$ is an automorphism of the graph iff there exists an isomorphism from $H_u$ to $H_v$. So, at most ${|V(G)| \choose 2}$ isomorphism tests should suffice to detect if the graph has a nontrivial automorphism. – AG. Dec 15 '13 at 6:37