# Linking and Cutting Spanning Trees
## 4 The Details
### Coupling
#### 4.2.2. \(d(x,y)=1\)  
If \(d(x,y)=1\) then the edges \(e_{x}\in A_{x}\setminus A_{y}\) and \(e_{y}\in A_{y}\setminus A_{x}\) exist and are distinct. We also need the following sets: \(I=C_{x}\cap C_{y}\), \(E_{x}=C_{x}\setminus I\) and \(E_{y}=C_{y}\setminus I\). The set \(I\) represents the edges that are common to \(C_{x}\) and \(C_{y}\). The set \(E_{x}\) represents the edges that are exclusive to \(C_{x}\), from the cycle point of view. This should not be confused with \(e_{x}\) which represents the edge that is exclusive to \(A_{x}\), i.e., from a tree point of view. Likewise, \(E_{y}\) represents the edges that are exclusive to \(C_{y}\). Also we consider the cycle \(C_{e}\) as the cycle contained in \(A_{x}\cup\{e_{y}\}\), which necessarily contains \(e_{x}\). The following Lemma describes the precise structure of these sets. **Lemma 1**. : _When \(i_{y}=i_{x}\) we either have \(C_{x}=C_{y}=I\) and therefore \(E_{x}=E_{y}=\emptyset\), or \(E_{x}\), \(E_{y}\) and \(I\) form simple paths, and the following properties hold:_  
* \(e_{x}\in E_{x}\)_,_ \(e_{y}\in E_{y}\)_,_ \(i_{x}\in I\)__
* \(E_{x}\cap E_{y}=\emptyset\)_,_ \(E_{x}\cap I=\emptyset\)_,_ \(E_{y}\cap I=\emptyset\)__
* \(E_{x}\cup I=C_{x}\)_,_ \(E_{y}\cup I=C_{y}\)_,_ \(E_{x}\cup E_{y}=C_{e}\)_._  
Notice that in particular this means that, in the non-trivial case, \(E_{x}\) and \(E_{y}\) partition \(C_{e}\). A schematic representation of this Lemma is shown in Figure 4.  
We have several different cases described below. Aside from the lucky cases 2 and 3, we will usually choose \(i_{y}=i_{x}\), as \(Y_{t}\) tries to copy \(X_{t}\). Likewise, if possible, we would like to set \(o_{y}=o_{x}\). When this is not possible we must choose \(o_{y}\in E_{y}\), ideally we would choose \(o_{y}=e_{y}\), but we must be extra careful with this process to avoid losing the behavior of \(M_{t}\). To maintain this behaviour, we must sometimes choose \(o_{y}\in E_{y}\setminus\{e_{y}\}\). Since \(X_{t}\) provides no information on this type of edges, we use  
Figure 4: Schematic representation of the relations between \(E_{x}\), \(E_{y}\), and \(I\). \(o_{y}=s_{y}\) chosen uniformly from this \(E_{y}\setminus\{e_{y}\}\), i.e., select from \(C_{y}\) but not \(e_{y}\) nor edges that are also in \(C_{x}\). There is a final twist to this choice, which makes the coupling non-Markovian, i.e., it does not verify the conditions in Equations (1a) and (1b). We can choose \(o_{y}=e_{y}\) more often than would otherwise be permissible by keeping track of how \(e_{y}\) was determined. If \(e_{y}\) is obtained deterministically, for example by the initial selection of \(x\) and \(y\), then this is not possible. In general \(e_{y}\) might be determined by the changes in \(X_{t}\), in which case we want to take advantage of the underlying randomness. Therefore, we keep track of the random processes that occur. The exact information we store is a set of edges \(U_{y}\subseteq C_{e}\setminus\{e_{x}\}\), such that \(e_{y}\in U_{y}\), and moreover this set contains the edges that are equally likely to be \(e_{y}\). This information can be used to set \(o_{y}=e_{y}\) when \(s_{y}\in U_{y}\), however after such an action the information on \(U_{y}\) must be purged. To illustrate the possible cases we use Figures 5-15, where the edges drawn with double lines represent a generic path that may contain several edges, or none at all. The precise cases are as follows:  
1. If the chain \(X_{t}\) loops (\(x^{\prime}=x\)), because \(i_{x}\in A_{x}\), then \(Y_{t}\) also loops and therefore \(y^{\prime}=y\). The set \(U_{y}\) does not change, i.e., set \(U_{y^{\prime}}=U_{y}\). 2. If \(i_{x}=e_{y}\) and \(o_{x}=e_{x}\) then set \(i_{y}=e_{x}\) and \(o_{y}=e_{y}\). In this case the chains do not coalesce; they swap states because \(x^{\prime}=y\) and \(y^{\prime}=x\) (see Figure 5). Set \(U_{y^{\prime}}=C_{e}\setminus\{e_{x^{\prime}}\}\). 3. If \(i_{x}=e_{y}\) and \(o_{x}\
eq e_{x}\) then set \(i_{y}=e_{x}\) and \(o_{y}=o_{x}\).