0
$\begingroup$

Let $G$ and $H$ be two connected graphs and $K$ be the disjoint union of them. Also assume that we can find generating permutation for $Aut(X)$ or any graph $X$. $G$ and $H$ are isomorphic if and only if some generator of $Aut(K)$ interchanges the two connected components. How do we prove this last statement? Please give the intuitive explanation.

Thank You.

1 Answers 1

1

Since the automorphisms of a graph are graph isomorphisms, an automorphism on $K$ is an isomorphism from $K$ to $K$. Now, assume that some automorphism $\phi$ of $K$ is given.

If $\phi(G) = H$ and $\phi(H) = G$, then (since $\phi$ is an injective graph homomorphism by construction and surjective by assumption), we have found a graph isomorphism from $G$ to $H$ via $\phi|_G$ (and, conversely, its inverse is $\phi|_H$). On the other hand, we can reverse this construction to turn a graph isomorphism $\psi: G \to H$ into an automorphism of $K$.