Graph puzzles,homotopy, and the alternating group

The so-called 15-puzzle may be generalized to a puzzle based on an arbitrary graph. We consider labelings or colorings of the vertices and the operation of switching one distinguished label with a label on an adjacent vertex. Starting from a given labeling, iterations of this operation allow one to obtain all, or exactly half, of the labelings on a non-separable graph (with the polygons and one other graph as exceptions).