# How to detect automorphism of union of graphs?

On page 1 of Lecture 2, Algebra and Computation , (Course Instructor: V. Arvind), there is a theorem-

Theorem 2. With Graph − Iso (graph isomorphism) as an oracle, there is a polynomial time algorithm for Graph − Aut (automorphism) and vice-versa.

on page 2, the proof is given-

Proof. First we shall show that we can solve Graph−Iso with Graph−Aut as an oracle. We are given two graphs $G_1$ and $G_2$ and we need to create a graph G using the two such that the generating set of the automorphism should tell us if they are isomorphic or not. Let $G = G_1 \cup G_2$. Suppose additionally we knew that $G_1$ and $G_2$ are connected, then a single oracle query would be sufficient. If any of the generators of $Aut(G)$ interchanged a vertex in $G_1$ with one in $G_2$, then connnectivity should force $G_1 \simeq G_2$. But what if they are not connected? We then have this very neat trick, $G_1 \simeq G_2 \Leftrightarrow \bar G_1\simeq \bar G_2$ , and either $G_1$ or $\bar G_1$ has to be connected and hence one can check for connectivity and then ask the appropriate query.

$\bar G_1$ is the complement graph of $G_1$, I assume.

It is said that-

Suppose additionally we knew that $G_1$ and $G_2$ are connected, then a single oracle query would be sufficient.

But when we test graph isomorphism, $G_1 , G_2$ are two different disconnected graph. Is it why it went on like-

But what if they are not connected? We then have this very neat trick, $G_1 \simeq G_2 \Leftrightarrow \bar G_1\simeq \bar G_2$, and either $G_1$ or $\bar G_1$ has to be connected and hence one can check for connectivity and then ask the appropriate query.

So, are we checking whether there is an automorphism of $G' = \bar G_1 \cup \bar G_2$ that swaps a vertex of $\bar G_1$ with a vertex of $\bar G_2$?

How can we tell that this kind of swapping is an automorphism?

• Example: $r$ is a permutation that swaps only 2 vertices of $G_1$ . Let, $G_1^{r} = G_2$. Let, $G= G_1 \cup G_2$. Clearly, $G$ is a disconnected graph, so we try $G' = \bar G_1 \cup \bar G_2$ instead of $G$. But how we detect an automorphism of $G'$ ? – Michael May 23 '16 at 20:29

Yes, you are checking whether there is an automorphism of $G^{\prime} = \bar{G}_{1} \cup \bar{G}_{2}$ that swaps a vertex of $\bar{G}_{1}$ with a vertex of $\bar{G}_{2}$. You are using Graph-Aut as an oracle, so what you will do is use Graph-Aut to find the automorphism group of $G^{\prime}$ (returned as a set of generators), then just look at whether any of these generators swap vertices of $G_{1}$ with those of $G_{2}$. You don't need to do anything to tell if this swapping is an automorphism, it is automatically an automorphism because it's returned by Graph-Aut.
• probably I am making a mistake here, does $G_1 \cup G_2$ has any edge between $G_1 , G_2$ ? similarly, does $\bar G_1 \cup \bar G_2$ has any has any edge between $\bar G_1 , \bar G_2$ ? – Michael May 24 '16 at 13:56
• @Jim No, $G_{1} \cup G_{2}$ is a disjoint union, so there are no edges between $G_{1}$ and $G_{2}$ (you want $G_{1}$ and $G_{2}$ to each be connected, but $G = G_{1} \cup G_{2}$ will be disconnected, with $G_{1}$ and $G_{2}$ being the connected components). – Morgan Rodgers May 24 '16 at 20:03