Exb 1

$\def\abs#1{|#1|}\def\i{\mathbf {i}}\def\ket#1{|{#1}\rangle}\def\bra#1{\langle{#1}|}\def\braket#1#2{\langle{#1}|{#2}\rangle}\mathbf{Exercise\ B.1}$

Let $G$ and $H$ be finite graphs. A map $f:G\to H$ is a {\it graph isomorphism}\index{graph isomorphism} if it is one-to-one and $f(g_1)$ and $f(g_2)$ have an edge between them if and only if $g_1$ and $g_2$ do. An {\it automorphism}\index{automorphism} of $G$ is a graph isomorphism from $G$ to itself, $f:G\to G$. A graph automorphism of $G$ is a permutation of its vertices.

The {\it graph isomorphism problem}\index{graph isomorphism problem} is to find an efficient algorithm for determining whether there is an isomorphism
between two graphs or not.

a) Show that the set $\mathrm{Aut}(G)$ of automorphisms of a graph $G$ forms a group, a subgroup of the permutation group $S_n$, where $n = |G|$.

b) Two graphs $G_1$ and $G_2$ are isomorphic if there exists at least one automorphism in $\mathrm{Aut}(G_1\cup G_2) < S^{2n}$ that maps nodes of $G_1$ to $G_2$ and vice versa. Show that if $G_1$ and $G_2$ are
non-isomorphic connected graphs, then $\mathrm{Aut}(G_1\cup G_2) = \mathrm{Aut}(G_1) \times \mathrm{Aut}(G_2)$.

c) Show that if $\mathrm{Aut}(G_1\cup G_2)$ is strictly bigger than $\mathrm{Aut}(G_1) \times \mathrm{Aut}(G_2)$, then there must be an element of $\mathrm{Aut}(G_1\cup G_2)$ that swaps $G_1$ and $G_2$.

d) Express the graph isomorphism problem as a hidden subgroup problem.