** Question :** Notice the inequality inside yellow box. If $i_1$ has $n$ possible vertex, then $j$ has maximum $(n-1)$ vertices. For $\mu_{i_1,j}$ , it should be $1\leq j \leq (n-1)$ .
but it is written that, $1\leq j \leq n$ . Why?
Relevent Question : what does $\mu_j(i)={ \begin{cases} 1 & If \ \ \ i=1 \\ 0 & Otherwise \end{cases} }$ mean?
- From "Lecture Notes in Computer Science" by Christoph M. Hoffmann
Ok, so the idea of the proof is to build an isomorphism from $X$ to $X'$. To do that they use labelling on the vertices.
The first paragraph state that you can know whether $X$ and $X'$ are isomorphic by checking whether $(X,0)$ and $(X',0)$ are (where $0$ is the labelling function that assign $0$ as the label of all vertices). Thus now we assume that $X$ and $X'$ are isomorphic.
Now thee idea is to find incrementally for each vertex of $X$ a matching vertex in $X'$.
For simplicity I denote $X=\{v_1,...,v_n\}$ and $X'=\{u_1, ...,u_n\}$
First they give a labelling $\lambda_1$ that label $v_1$ with $1$ and all other $v_j$ (with $j>1$) with $0$. And $\mu_j$ label $u_j$ with $1$ and all the other $u_i$ (with $i\neq j$) with 0.
Since $X$ and $X'$ are isomorphic we know that there exist an isomorphism between $X$ and $X'$ and that isomorphism must match $v_1$ with some $u_{i_1}\in X'$. Hence, for $(X,\lambda_1)$ and $(X,\mu_{i_1})$ are isomorphic.
So we have found the first matching for $v_1$ witch is $u_{i_1}$. We will now look for a vertex matching $v_2$ assuming that $v_1$ is matched by $u_{i_1}$.
To do this we use other labelling function. Since $v_1$ is matched by $u_{i_1}$ we label them by the same thing $1$. Since we look for a matching for $v_2$ we label it by a new label: 2. to find the good match we try all the possible labelling for $X'$ that assign $1$ to $u_{i_1}$ and $0$ to all other vertex except for one which is labeled by $2$. This vertex is the candidate for being the matching of $v_2$. They denote such labelling by $\mu_{i_1,j}$, where $i_1$ is the matching for $v_1$ and $j$ is the candidate matching for $v_2$.
With the same argument as before we know that there exists an isomorphism, thus there exists a matching for $v_2$ thus there exists $i_2$ such that $(X,\lambda_2)$ is isomorphic to $(X',\mu_{i_1,i_2})$.
And you continue like that until you found $i_1,i_2,...,i_n$ with is an isomorphism for $X$ to $X'$.
So to address your question, the only think we know on $i_1$ is that $1\leq i_1\leq n$.
The only think we know on $i_2$ is that $i_1\neq i_2$ and $1\leq i_2 \leq n$. (That why the contain on $j$ when defining the $\mu_{i_1,j}$ is $i_1\neq j$ and $1\leq j \leq n$). Indeed $1\leq j \leq n$ does not give a bound on the number of possible candidates for the label $2$ it only says that this candidate is a vertex of $X'$. The only thing that gives you a 'bound' is to know that it cannot be $i_1$.
I hope it helps you