uniform spanning tree of $2 \times n$ graph In Probability on Trees and Networks Chapter 1 study the uniform spanning tree on the ladder graph:
 _
|_|
|_|
|_|
...
|_|
|_|

The probability the bottom rung appears in a uniform spanning tree of this graph is $\sqrt{3}-1$ and for finite ladders, the probabilities are continued fraction convergents.
 _    _   
| |  |_  |_|
| |  |_  |_
 _|  | |  _|
 _|  |_  |
 _|  | | |_|

Why is the limit $\sqrt{3}-1$ and why do continued fractions appear here?

Here is a uniform spanning tree of a ladder graph and indeed, you get the bottom rung 7 in 10 times.


Maybe the identity $\frac{1}{\sqrt{3}-1} = \frac{\sqrt{3}+1}{2}$ may be useful.
 A: In general when a continued fraction appears a recurrence is near. I don't understand at all why you gave just 3 examples of a spanning tree for a ladder of height 5, and then 10 example spanning trees for a ladder of height 21 if I didn't count wrongly. I assume they were randomly generated, in which case it cannot prove anything because it was pure luck that you got 7 of 10 having the bottom rung. To numerically prove the theorem you'll have to generate all spanning trees and count what proportion has the bottom rung.
To prove the theorem we should set up a recurrence. We can build the spanning tree one level at a time from top to bottom, starting from two vertices which are either joined by an edge or not. At each step we add two vertices below and potentially some of the 3 edges up to that depth, which is 2 vertical edges and 1 horizontal edge. Notice that it is important to know whether the currently built graph is connected. If it is not, the two pieces must be each be connected to one of the two current bottom vertices and the two bottom vertices must not be joined, otherwise the graph can never be connected by the subsequent building. We also need to know whether the current bottom vertices are connected, so that when we finish building we can count separately how many have the bottom rung. These give the following 3 cases:
Let $a(k) = ( \text{number of connected built graphs of depth }k\text{ that have a bottom edge} )$
Let $b(k) = ( \text{number of connected built graphs of depth }k\text{ that have no bottom edge} )$
Let $c(k) = ( \text{number of disconnected built graphs of depth }k\text{ that have no bottom edge} )$
Now it is easy to verify the following recurrences:
$a(k+1) = 2 a(k) + 2 b(k) + c(k)$
$b(k+1) = a(k) + b(k)$
$c(k+1) = 2 a(k) + 2 b(k) + c(k)$
We let the starting depth be $0$, and so we have:
$a(0) = 1$
$b(0) = 0$
$c(0) = 1$
Clearly $a(k) = c(k)$ for all natural $k$, so the recurrences simplify to:
$a(k+1) = 3 a(k) + 2 b(k)$
$b(k+1) = a(k) + b(k)$
Recall that we want $\frac{a(n)}{a(n)+b(n)}$, since we want the final built graph to be connected, and we want to find the proportion that has a bottom edge.
From here you can solve the recurrence to get the general formula and get the limit, if that is all you need. If you want to prove that the ratio is also a convergent of the continued fraction for $\sqrt{3}-1$, then you can do the following:
Let $t(k) = a(k) + b(k)$
$a(k+1) = 3 a(k) + 2 b(k) = a(k) + 2 t(k)$
$t(k+1) = 4 a(k) + 3 b(k) = a(k) + 3 t(k)$
Now all we have to do is to establish the same recurrence for the convergents of the continued fraction for $\sqrt{3}-1$.
$\sqrt{3}-1 = \frac{2}{2+\frac{2}{2+...}}$
Given any convergent $\frac{p}{q}$, the next convergent will be $\frac{2}{2+\frac{p}{q}} = \frac{2q}{p+2q}$, and the subsequent convergent will be $\frac{2}{2+\frac{2q}{p+2q}} = \frac{p+2q}{p+3q}$, and so we are done.
