Let $f$ be a map from a finite graph $G$ to itself.
Then
- $f$ is an homomorphism if $f(x)$ and $f(y)$ are adjacent for all adjacent vertices $x$ and $y$ in $G$.
- $f$ is an automorphism if, for all vertices $x$ and $y$ in $G$, $x$ and $y$ are adjacent if and only if $f(x)$ and $f(y)$ are adjacent.
If $f$ is a bijective homomorphism, how do I show it is also an automorphism? I've seen a proof of the equivalent statement for groups but I can't see how to translate it to the language of graph theory.
Suppose $G$ has $m$ edges and $f: G \to G$ is a bijective homomorphism. Then each pair of adjacent vertices determines an edge on the image of $f$. Thus there exist $m$ edges in the image of $f$, which are all distinct because $f$ is injective. Let $x$ and $y$ be non-adjacent vertices in $G$. Then $f(x)$ and $f(y)$ are also non-adjacent, otherwise the image of $f$, which is contained in $G$, would have $m + 1$ edges. Hence $f$ is an automorphism.