Restriction on Graph Automorphism

Question

This question referes to a definition in Eugene M. Luks paper "Isomorphism of Graphs of Bounded Valence Can Be Tested in Polynomial Time" (1981), page 48, available at http://ix.cs.uoregon.edu/~luks/iso.pdf‎.

Let $X$ be a (simple, undirected) trivalent graph (that is, a graph with max node degree 3) and let $e$ be a distinguished edge in $X$. For $r \in \{1,...,n\}$, let $X_r$ be the subgraph consisting of all vertices and all edges of $X$ which appear in paths of length $\leq{}r$ trough $e$. Let $\text{Aut}_e(X_r)$ be the subgroup of $\text{Aut}(X_r)$ containing all automorphism that fix edge $e$.

It is claimed without proof that $\pi_r: \text{Aut}_e(X_{r+1}) \to \text{Aut}_e(X_r)$, $\sigma \mapsto \sigma|_{X_r}$ (i.e, every automorphism on $X_{r+1}$ is restricted to $X_r$) is a group homomorphism.

However, I do not see how the restriction of any $\sigma\in\text{Aut}_e(X_{r+1})$ is a automorphism on $X_r$ and thus a member of $\text{Aut}_e(X_r)$. Moreover, I think I found a counterexample:

Let $X$ be the fully connected graph with three vertices $v_0,v_1,v_2$. Let the distinguished edge $e=(v_0,v_1)$. Then $X_1$ is the graph with nodes $v_0,v_1$ and edge $e$. $X_2 =X$. Therefore, $\text{Aut}_e(X_1)$ is isomorphic to $S_2$ (containing two elements, the identity and the transposition of both nodes). The automorphism group of $X_2$ however is isomorphic to $S_3$, which also contains the rotation of the nodes. Thus, let $\sigma$ be the rotation $v_i \mapsto v_{i+1}$ with addition modulo 3. Then, for the restriction of $\sigma$ to $X_1$ it holds $\sigma|_{X_1}(v_2) = v_3 \notin X_1$, and therefore $\sigma|_{X_1} \notin \text{Aut}_e(X_1)$. Thus, $\pi_2$ cannot be a group homomorphism $\text{Aut}_e(X_{2}) \to \text{Aut}_e(X_1)$.

I suppose I am missing something. What is it?

Answer 1

The counterexample given (ie. the rotation) is not an element of $\text{Aut}_e(X_{r+1})$, because it doesn't fix edge $e$. It is therefore not a counterexample.

Answer 2

Any graph automorphism must map paths to paths. This can be seen by induction.

Use the definition of a graph homomorphism as the base case (that is, $x\sim y \Rightarrow \psi(x)\sim \psi(y)$). Now assume that $x_1x_2\ldots x_nx_{n+1}$ is a path of length $n+1$. Then $x_1x_2\ldots x_n$ is a path of length $n$, so by inductive hypothesis, $\psi(x_1)\psi(x_2)\ldots \psi(x_n)$ is a path. Now, since $x_n\sim x_{n+1}$, we have $\psi(x_n)\sim \psi(x_{n+1})$, so we have that $\psi(x_1)\psi(x_2)\ldots \psi(x_n)\psi(x_{n+1})$ is a path.

In particular, paths of length at most $n$ are mapped to paths of length at most $n$. Therefore, if $\psi$ is any automorphism of a graph $\Gamma$ containing $X_r$ such that $\psi(e)=e$, we have that $\psi(X_r)\subseteq X_r$, and because $\psi$ is bijective, this means that $\psi(X_r)= X_r$. So, $\psi_{X_r}\in \operatorname{Aut}_e(X_r)$.

Using the same technique, it's easy to see that given two graph automorphisms $\psi$ and $\phi$ fixing $e$, $\psi\phi$ behaves the same in $X_r$ as it does in $\Gamma$. So the restriction map preserves the group structure.