$\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)$?