\def\puz{\mathop{\strut\mathrm{puz}}}
A path in a graph G is a sequence p=(v_0,\ldots,v_k) of vertices such that v_i is adjacent to v_{i+1}; the length of the path is k. It is a simple path if the vertices are distinct, or if \{v_0,\ldots,v_{k-1}\} are distinct and v_k=v_0, in which case it is a simple closed path. We denote the path (v_k,\ldots,v_0) by \overline p, the reverse of p.
Given path p, define a permutation \sigma_p\colon V(G)\to V(G) by \sigma_p=(v_k,v_{k-1})\cdots(v_2,v_1)(v_1,v_0) =(v_k,v_{k-1},\ldots,v_1,v_0).
Proposition 2.2.1 Labelings f and g of G are in the same component of \puz(G) if and only if f=g\sigma_p for some path p from f^{-1}(\emptyset) to g^{-1}(\emptyset).
Proof. Given f=g(g^{-1}(\emptyset),v_{k-1})(v_{k-1},v_{k-2})\cdots(v_1,f^{-1}(\emptyset)), let h_i=g(g^{-1}(\emptyset),v_{k-1})\ldots(v_{i+1},v_i), so that \eqalign{ g&\cr h_{k-1}&=g(g^{-1}(\emptyset),v_{k-1}),\cr h_{k-2}&=h_{k-1}(v_{k-1},v_{k-2}),\cr \vdots&\cr h_1&=h_2(v_2,v_1),\cr f&=h_1(v_1,f^{-1}(\emptyset))\cr } is a path from g to f in \puz(G).
If f and g are in the same component, then there are permutations h_1,\ldots,h_{k-1} such that h_{k-1}=g(g^{-1}(\emptyset),v_{k-1}), h_{k-2}=h_{k-1}(v_{k-1},v_{k-2}),…, h_1=h_2(v_2,v_1), f=h_1(v_1,f^{-1}(\emptyset)). Thus, with p=(f^{-1}(\emptyset),v_1,v_2,\ldots,v_{k-1},g^{-1}(\emptyset)), f=g\sigma_p. \qed
Definition 2.2.2 Let \Gamma(v,w)=\Gamma_G(v,w) be the set of all permutations \sigma_p where p is a path from v to w. We use \Gamma(v)=\Gamma_G(v) to denote \Gamma(v,v). \square
Definition 2.2.3 If p is a path from u to v, and q is a path from v to w, we denote by pq the path from u to w consisting of p followed by q. \square
The following lemma is easy.
Proposition 2.2.5 For all v of G, \Gamma(v) is a group of permutations, all of which fix v. If p is a path from v to w, then \Gamma(v,w)=\sigma_p\Gamma(v)=\Gamma(w)\sigma_p, and consequently \Gamma(w)=\sigma_p\Gamma(v)\sigma_p^{-1}.
Proof. It is easy to check that \Gamma(v) is a group.
Suppose q is a path from v to w. Then \sigma_q=\sigma_p\sigma_{\overline p}\sigma_q, and since \sigma_{\overline p}\sigma_q=\sigma_{q\overline p}\in\Gamma(v), \Gamma(v,w)\subseteq\sigma_p\Gamma(v).
Suppose q is a path from v to v. Then \sigma_p\sigma_q=\sigma_{qp}\in \Gamma(v,w), so \Gamma(v,w)\supseteq\sigma_p\Gamma(v). Thus \Gamma(v,w)=\sigma_p\Gamma(v).
The proof that \Gamma(v,w)=\Gamma(w)\sigma_p is essentially identical. \qed
Recall that the symmetric group on a set X=\{x_1,\ldots,x_n\} is the group of all permutations of X, which we denote S(X), and the alternating group on X is the set of all even permutations on X, denoted A(X).
Of particular interest will be the theta graphs, or \theta-graphs. A \theta-graph consists of a cycle plus an additional path whose endpoints are two distinct vertices, say v and w, of the cycle. The graph thus consists of three internally disjoint paths from v to w, with a, b, and c internal vertices. We will say this is the \theta-graph of type (a,b,c), and without loss of generality, we usually ensure a\ge b\ge c. We will need to single out a particular \theta-graph, \theta_0, of type (2,2,1):
Most of our effort will be in proving the following lemma.
Lemma 2.2.6 Let G be a simple 2-connected graph on n vertices, other than a cycle or the graph \theta_0. Then, for any vertex v of G, \Gamma(v) is the symmetric group on V(G)\backslash\{v\}, unless G is bipartite, in which case \Gamma(v) is the alternating group on V(G)\backslash\{v\}. \qed
Our principal theorem is
Theorem 2.2.7 Let G be a simple 2-connected graph on n vertices, other than a cycle or the graph \theta_0. Then \puz(G) is connected unless G is bipartite. If G is bipartite, \puz(G) has exactly two components, and if labelings f and g have unoccupied vertices at distance d from each other, then f and g are in the same component if and only if g^{-1}f is a permutation of V(G) with the same parity as d.
Proof. Let G be a simple 2-connected graph and v a vertex of G. Each component of \puz(G) contains an f with f(v)=\emptyset. Labelings f and g, with g(v)=\emptyset, are in the same component if and only if f=g\sigma_p, where p is a path from v to v. That is, f and g are in the same component if and only if g^{-1}f\in \Gamma(v).
Fix a labeling h with h(v)=\emptyset. For any labeling g, let \tau_g=h^{-1}g. The map g\mapsto \tau_g is a bijection from the set of labelings that map v to \emptyset to S(V(G)\backslash\{v\}). Now we have g^{-1}f\in \Gamma(v) if and only if (h\tau_g)^{-1}h\tau_f\in \Gamma(v) if and only if \tau_g^{-1}\tau_f\in \Gamma(v) if and only if \tau_f\Gamma(v)=\tau_g\Gamma(v). Thus, the components of \puz(G) are in 1–1 correspondence with the cosets of \Gamma(v) in S(V(G)\backslash\{v\}).
By lemma 2.2.6, \Gamma(v) is either S(V(G)\backslash\{v\}) or A(V(G)\backslash\{v\}). If the former, there is one coset and hence \puz(G) is connected.
If \Gamma(v)=A(V(G)\backslash\{v\}), suppose that f(v)=g(w)=\emptyset, and let p be a path from v to w. Then f and g are in the same component if and only if g^{-1}f\in \Gamma(v,w)=\sigma_p\Gamma(v) if and only if g^{-1}f and \sigma_p have the same parity if and only if g^{-1}f and the length of p have the same parity. \qed
The proof of lemma 2.2.6 is by induction. By proposition 2.2.5, it suffices to prove the lemma for a single v. Also, it will suffice to show that A(V(G)\backslash\{v\})\subseteq \Gamma(v), since \Gamma(v) contains an odd permutation if and only if G contains an odd length closed path if and only if G is not bipartite.
Exercises 2.2
Ex 2.2.1 Prove lemma 2.2.4.
Ex 2.2.2 Prove that \Gamma(v) is a group, as claimed in proposition 2.2.5.
Ex 2.2.3 Let G be a cycle on n vertices. How many components are in \puz(G)? What is \Gamma(v)?