group of Automorphisms

107 Views Asked by At

A graph is an ordered pair $G = (V, E)$ comprising a set $V$ of vertices together with a set $E$ of edges which are $2$-element subsets of $V$ , i.e., $E \subseteq \{(u, v)\mid u, v \in V \}$.

An automorphism of a graph $G = (V, E)$ is a permutation $\sigma$ on the vertex set $V$ , such that the pair of vertices $(u, v) \in E$ if and only if the pair $(\sigma(u), \sigma(v)) \in E$.

Now consider the set of all such automorphisms and let us denote this set as Aut($G$). Prove that Aut($G$) forms a group under composition operation.

1

There are 1 best solutions below

0
On

Here's a proof that it has inverses.

Let $\sigma \in \operatorname{Aut}(G)$.

We have that for any $(u,v) \in E$ that $\sigma(u,v)=(\sigma(u),\sigma(v))$.

Since $\sigma$ is a permutation, it is bijective, so there exists a permutation $\sigma^{-1}$ on $V$ such that $\sigma^{-1}\circ \sigma = \sigma\circ \sigma^{-1}= id$.

We need to show that $(u,v)\in E \iff (\sigma^{-1}(u), \sigma^{-1}(v)) \in E$

Since $\sigma^{-1}$ is a permutation on $V$, we know that $(\sigma^{-1}(u), \sigma^{-1}(v))$ is a pair of vertices, and since $\sigma \in \operatorname{Aut}(G)$, we have

$$(\sigma^{-1}(u), \sigma^{-1}(v)) \in E \iff(\sigma(\sigma^{-1}(u)),\sigma(\sigma^{-1}(v)) ) \in E$$

But $\sigma\circ \sigma^{-1} =id$, so we have

$$(\sigma^{-1}(u), \sigma^{-1}(v)) \in E \iff(u,v) \in E$$

Which is what we wanted to show. This means that $\sigma^{-1} \in \operatorname{Aut}(G)$.