Number of edges of a random connected undirected graph created by a random walk Consider the following algorithm that generates a random connected undirected graph with $n$ vertices.

Choose a random starting vertex and perform a random walk as follows. At each step $i$ of the walk, let $v_i$ be the vertex we are currently at. Choose a random vertex $v_{i+1}$ and walk to $v_{i+1}$ at the next step. If $ v_i \neq v_{i+1} $ and $ \{v_i, v_{i+1}\} $ has not been walked, add $ \{v_i, v_{i+1}\} $ to the set of (undirected) edges. (Even if $ v_i = v_{i+1} $, we still perform the walk. We just 'wasted' one step). Stop when all $n$ vertices have been visited.

The graph $G_n$ obtained this way is guaranteed to be connected. Now the problem is:
What is the probability distribution of the number $M_n$ of edges of $G_n$? If this is too hard to find, what about the expected number $\text{E}[M_n]$?
I know $ \text{E}[M_n] = O(n\log n) $, because the expected number of the steps $N_n$ needed is exactly
$$ \text{E}[N_n] = n \sum_{i=1}^n \frac{1}{i} = O(n\log n) $$
But is there an exact formula for $ \text{E}[M_n] $? Better yet, can we find the probability distribution of $M_n$?
 A: Consider a state of the system to consist of a connected set of edges plus a vertex that (if the set of edges is nonempty) is on that set of edges.  We start with the empty set and a random vertex, and perform a Markov chain.  The usual recursive techniques can compute the probability of ending in each of the terminal states (where the set of edges includes all vertices).  Note that the final vertex will always have degree $1$.
The simplest nontrivial case is $n=4$.  Allowing for symmetries, there are the following states (with the latest vertex shown highlighted in red). 

The Markov chain has the following transition matrix.
$$ \pmatrix{1/4 & 3/4 & 0 & 0 & 0 & 0 & 0 & 0\cr
            0 & 1/4 & 0 & 3/4 & 0 & 0 & 0 & 0\cr
            0 & 0 & 1/4 & 1/2 & 0 & 1/4 & 0 & 0\cr
            0 & 0 & 1/4 & 1/4 & 1/4 & 0 & 1/4 & 0\cr
            0 & 0 & 0 & 0 & 3/4 & 0 & 0 & 1/4\cr
            0 & 0 & 0 & 0 & 0 & 1 & 0 & 0\cr
            0 & 0 & 0 & 0 & 0 & 0 & 1 & 0\cr
            0 & 0 & 0 & 0 & 0 & 0 & 0 & 1\cr} $$
I find that starting in state $0$, the probabilities of ending in the three terminal states $6,7, 8$ are $1/7$, $3/7$ and $3/7$ respectively.  Thus the number of edges in the final state is $3$ with probability $4/7$ and $4$ with probability $3/7$.  
I would expect that for large $n$ the probability distribution will get quite complicated.
