Let $X$ be a trivalent graph. We denote by ${\rm Aut}_e(X)$ the subgroup of ${\rm Aut}(X)$ such as fix the edge $e$. Here $X_r$ is the subgraph consisting of all vertices and all edges of the graph$X$ which appear in paths of length $\leq r$ through $e = (a, b)$.
We notice that, $\textbf{any permutation}$ $\tau$ of $\rm Aut_e(X_{r+1})$ is the the product of disjoint permutation of $\tau_{V(X_{r+1})\setminus V(X_{r})}$ and $\tau_{V(X_{r})}$, i.e. $$\tau = \tau_{V(X_{r+1})\setminus V(X_{r})} \cdot \tau_{V(X_{r})} \cdots (1)$$
,where $\tau_{V(X_{r+1}\setminus V(X_{r})}$ is a permutation acting on the domain of vertices of $V(X_{r+1})\setminus V(X_{r})$
,and $\tau_{V(X_{r})}$ is a permutation acting on the domain of vertices of $ V(X_{r})$
, since any automorphism of the graph $X_{r+1}$ also $\textbf{has to be}$ the automorphism of the subgraph $X_r$ of the graph $X_{r+1}$ by the definition of automorphism, so by definition, $\tau_{V(X_{r})} \in \rm Aut_e(X_{r})$.
In the literature, we find phrase like "extend to an element" (Polynomial Time GI of Bounded Valence, E. M. Luks, proposition 2.3, page 49) or "By approximation" (Algebra and Computation by V. Arvind, page 28),
it means that, for any $\sigma= \tau_{V(X_{r})} \in \rm Aut_e(X_r)$,
"extending" $\sigma$ is the "approximation" of $\tau \in \rm Aut_e(X_{r+1})$
such that $\sigma$ is a $\textbf{disjoint permutation factor}$ of $\tau$ $\textbf{(informally speaking, each automorphism of $X_{r+1}$}$ $\textbf{ must have an automorphism of $X_r$ as factor})$.
With this information, clearly, for each $\tau \in \rm Aut_e(X_{r+1})$, we can relate a $\sigma \in \rm Aut_e(X_{r})$ with $\tau$, i.e., for each $\tau$ there is a $\sigma$, this relation is denoted by $\pi_r$ and defined as $\pi_r:\rm Aut_e(X_{r+1}) \rightarrow \rm Aut_e(X_{r})$ by $\pi_r(\tau) = \sigma$, according to equation $(1)$, $\pi_r(\tau) = \tau_{V(X_{r})}$.
Proof that $\pi_r$ is a surjection:
The function $\pi_r$ is a surjective (onto) function, because if there exists a $\tau \in \rm Aut_e(X_{r+1})$, then from equation $(1)$, we see that $\tau_{\kappa}$ is also an automorphism of $X_{r+1}$ where $\tau_{\kappa} = \tau_{V(X_{r+1})\setminus V(X_{r})} \cdot \kappa_{V(X_{r})}$, for $\textbf{any}$ $\kappa \in \rm Aut_e(X_r)$, so each element of $\rm Aut_e(X_r)$ has relation with elements of $\rm Aut_e(X_{r+1})$, implying an onto function.
Thus, we prove the existence of the "induced homomorphism" $\pi_r$(Polynomial Time GI of Bounded Valence, E. M. Luks,page 48).
QUESTIONS
Are the explanations of "extending", "approximation" correct?
Is the proof of the existence of the induced homomorphism $\pi_r$ correct?
Is the proof that $\pi_r$ is surjective correct?
EDIT 1:
- Answer to the question 3 is no, as it is pointed out in the comment.
Aim: Provide explanations for the beginners of the Trivalent Graph Isomorphism.
Acknowledgement: Nils Wisiol, LionsWrath and others (communicated through digital communication).