Permutation of the connected components of a graph under a graph automorphism I was wondering how to prove that an automorphism of an undirected graph induces a permutation of the set of the connected components of the graph.
I know that an undirected graph is a couple $(V,E)$ where $V$ is a set of vertices and $E\subseteq \mathcal{P}(V)$ consists of subsets of the form $\{x,y\}$ for some $x,y\in V$ ($\{x,y\}$ is the edge linking the vertices $x$ and $y$).
Furthermore, an automorphism of the graph is a map $\phi:V\to V$ which is bijective and is such that for any $x,y\in V$, if $\{x,y\}\in E$, then $\{\phi(x),\phi(y)\}\in E$. I understand intuitively what the connected components are and the fact that they partition the vertex set $V$. So we can write $V=\cup_{i=1}^n C_i$, where $C_i$ is the $i$-th connected component (I assume that $V$ is a finite set). My goal is to prove that the automorphism $\phi$ induces a permutation $\bar{\phi}$ of the set $\mathcal{C}=\{C_i:i=1,\dots ,n\}$ defined in the natural way: $\bar{\phi}(C_i)=\phi(C_i)$. To prove this I think I have to show that $\phi$ maps every connected component to another connected component, so that $\bar{\phi}:\mathcal{C}\to \mathcal{C}$ , and that $\bar{\phi}$ is bijective. But I don't know how to do this proof. Can you help me? Thanks! 
 A: An automorphism of a graph preserves distances. Thus, if $x,y \in V$ and $\phi$ is an automorphism of the graph, then $d(x,y) = d(\phi(x), \phi(y))$, where $d(a,b)$ denotes the length of a shortest $a-b$ path. We define $d(a,b)$ to be infinity if there is no $a-b$ path in the graph (ie if vertices $a$ and $b$ are in different connected components of the graph). Observe that if $x, y \in V$, then $d(x,y) < \infty$ iff $x$ and $y$ are in the same connected component of the graph.
To prove that an automorphism preserves distances, suppose $d(x,y) = k$ and suppose $x=u_0, u_1, \ldots, u_k=y$ is a shortest $x-y$ path in the graph. Then, $\phi(x) = \phi(u_0), \ldots, \phi(u_k)=\phi(y)$ is a path of length $k$ between $\phi(x)$ and $\phi(y)$. Hence, $d(\phi(x), \phi(y)) \le d(x,y)$.  The opposite inequality can be proved by applying $\phi^{-1}$. Hence, $d(x,y) = d(\phi(x), \phi(y))$. 
Let $C_1, \ldots, C_n$ be the connected components of the given graph and let $\phi$ be an automorphism of the graph.  If $x,y \in C_i$ for some $i$, then $d(x,y)$ is finite, whence $d(\phi(x), \phi(y))$ is also finite and so $\phi(x)$ and $\phi(y)$ are in the same connected component of the graph.
