More formally, a labeling is a bijection $f\colon V(G)\to [n]\cup\{\emptyset\}$. Two labelings $f$ and $g$ are adjacent if either may be obtained from the other by a legal move; that is, if $f(v)=\emptyset$, and $w$ is a neighbor of $v$, $g=f\circ(v,w)=f(v,w)$, where $(v,w)$ is the bijection transposing $v$ and $w$. (We will generally leave out the composition operator "$\circ$''.) Thus $g(v)=f(w)$, $g(w)=f(v)=\emptyset$, and otherwise $g(x)=f(x)$.

We define a new simple graph $\puz(G)$ as follows: the vertex set $V(\puz(G))$ contains all labelings of $G$, and two labelings are adjacent in $\puz(G)$ if and only if they are adjacent as defined in the previous paragraph. Now given initial labeling $f$ and goal labeling $g$, the question we want to answer is: Are $f$ and $g$ in the same connected component of $\puz(G)$? Our principal result will be that for almost all 2-connected graphs $G$, $\puz(G)$ has one or two connected components, and when there are two, we provide an easy way to determine when $f$ and $g$ are in the same component. The proof is due to R. M. Wilson, Graph puzzles, homotopy, and the alternating group, Journal of Combinatorial Theory (B), 16 (1974), pp. 86-96.

Exercises 2.1

Ex 2.1.1 Prove that from the "standard'' position shown in figure 2.1.1 it is not possible to produce the position shown below.