# Linking and Cutting Spanning Trees
## 4 The Details
### Coupling
#### 4.2.2. \(d(x,y)=1\)
This case is determined by the fact that \(o_{x}\in I\setminus\{i_{x}\}\) and sets \(o_{y}=o_{x}=o\). We make the following deduction, that uses the fact that the events are independent and the success probability of \(B\): Figure 4:7 Figure 4:8 Figure 4:9 Figure 5:0
* \(o\in E_{y}\setminus\{e_{y}\}\): this occurs in case 4.\(b\).iv, but also in cases 4.\(b\).iii and 4.\(b\).i when \(B\) is false. We have the following deduction, that uses event independence, the fact that the cases are disjoint events, and the success probability of \(B\): Figure 5:1 Figure 5:2 Figure 5:3 Figure 5:4 Figure 5:5 Figure 5:6 Figure 5:7 Figure 5:8 Figure 5:9 Figure 7:0 Figure 7:1 Figure 7:2 Figure 7:3 Figure 7:4 Figure 7:5
* When \(C_{x}>C_{y}\), this concerns case 4.\(c\). The cases for \(o\) are the following:* \(o=e_{y}\): this occurs in the case 4.c.i and case 4.c.iv when \(B^{\prime}\) is true. We use the following deduction: Figure 7:6 Figure 7:7 Figure 7:8 Figure 7:9 Figure 10:0 Figure 10:1 Figure 10:2 Figure 10:3 Figure 10:4 Figure 10:5 Figure 10:6 Figure 10:7
* \(o\in I\setminus\{i_{y}\}\): this occurs in case 4.c.ii and case 4.c.iii when \(B^{*}\) is true. We make the following deduction: Figure 10:8 Figure 10:9 \[p=\frac{C_{x}-1}{C_{y}-1}\]0 \[p=\frac{C_{x}-1}{C_{y}-1}\]1 \[p=\frac{C_{x}-1}{C_{y}-1}\]2 \[p=\frac{C_{x}-1}{C_{y}-1}\]3 \[p=\frac{C_{x}-1}{C_{y}-1}\]4 \[p=\frac{C_{x}-1}{C_{y}-1}\]5
* \(o\in E_{y}\setminus\{e_{y}\}\): this occurs in case 4.c.iv when \(B^{\prime}\) is false. We have the following deduction: \[p=\frac{C_{x}-1}{C_{y}-1}\]6 \[p=\frac{C_{x}-1}{C_{y}-1}\]7 \[p=\frac{C_{x}-1}{C_{y}-1}\]8 \[p=\frac{C_{x}-1}{C_{y}-1}\]9 Figure 11:0 Figure 11:1  
**Lemma 3**. : _The process we described is a non-Markovian coupling._  
Proof. : In the context of a Markovian coupling we analyze the transition from \(y\) to \(y^{\prime}\) given the information about \(x\). In the non-Markovian case we will use less information about \(x\). We assume that \(e_{y}\) is a random variable and that \(x\) provides only \(e_{x}\) and \(U_{y}\); we know only that \(e_{y}\in U_{y}\) and moreover that \(\Pr(e_{y}=e)=1/U_{y}\) for any \(e\in U_{y}\) and \(\Pr(e_{y}=e)=0\) otherwise. Then the chain \(X_{t}\) makes its move and provides information about \(i_{x}\) and \(o_{x}\). Let us consider only the cases when \(Y_{t}\) and choose \(i_{y}=i_{x}\), because nothing changes in the cases where this does not happen. Now, \(i_{x}\) can be used to define \(C_{x}\) and \(C_{y}\) and, therefore, \(E_{x}\) and \(E_{y}\). We focus our attention on \(E_{y}\cap U_{y}\) because, except for the trivial cases, we must have \(e_{y}\in(E_{y}\cap U_{y})\). Hence, we instead alter our condition to \(\Pr(e_{y}=e)=1/|E_{y}\cap U_{y}|\), for any \(e\in(E_{y}\cap U_{y})\) and \(0\) otherwise. Note that this is a reasonable process because we established in Lemma 1 that, in the non-trivial case, \(E_{x}\) and \(E_{y}\) partition \(C_{e}\) and, therefore, because \(U_{y}\subseteq C_{e}\setminus\{e_{x}\}\), we have that \(E_{x}\) and \(E_{y}\) also partition \(U_{y}\). This means that \(U_{y}\cap I=\emptyset\) and so we are not losing any part of \(U_{y}\) in this process; we are only dividing it into cases. This process is also the reason why, even when \(s_{y}\
otin U_{y}\), we define \(U_{y^{\prime}}=(U_{y}\cap C_{y})\setminus\{o_{y}\}=(U_{y}\cap E_{y})\setminus \{o_{y}\}\). Now the cases considered in Lemma 2 must be changed. Substitute the original cases of \(o=e_{y}\) for \(o\in U_{y}\cap E_{y}\). Also, substitute the case \(o\in E_{y}\setminus\{e_{y}\}\) for \(o\in E_{y}\setminus U_{y}\). The other cases remain unaltered. Except for the first case, the previous deductions still apply. We will exemplify how the deduction changes for \(o\in U_{y}\cap E_{y}\). We consider only the situation when \(|C_{x}|=|C_{y}|\). For the remaining situations, \(C_{x}<C_{y}\) and \(C_{x}>C_{y}\), we use a general argument. Hence our precise assumptions are: \(o\in U_{y}\cap E_{y}\) and \(|C_{x}|=|C_{y}|\).