$\def\puz{\mathop{\strut\mathrm{puz}}}$

Let's return to the 15-puzzle. In graph form, this is a bipartite graph, so we know that $\puz(G)$ has two components. We are interested in the component that contains the "standard'' labeling shown in figure 2.1.1; call this labeling $f$. Suppose that $g$ is a labeling with the same blank vertex. By theorem 2.2.7, $g$ is in the same component as $f$ if and only if $g^{-1}f$ has the same parity as $0$, that is, that $g^{-1}f$ is an even permutation of the vertices. In general, $g$ is in the same component as $f$ if and only if $g^{-1}f$ has the same parity as the distance that the blank in $g$ is from its original location.

It is a little more natural to think of permuting the labels, rather than the vertices. The corresponding permutation of the labels is $fg^{-1}$, which has the same parity as $g^{-1}f$. Thus it is easy to determine which configurations can be reached in the puzzle.

Exercises 2.5

Ex 2.5.1 Show that $fg^{-1}$ has the same parity as $g^{-1}f$.

Ex 2.5.2 Which of the following configurations can be produced from the standard starting position?