We are going to build $K\_n$ one edge at a time. Begin with the empty graph on $n$ vertices. Take a random permutation of the edges of $K\_n$ and, one at a time, place the edges onto the graph (so, after the $k$th edge in the list is placed, the so-far created graph will have exactly $k$ edges).


Let $H\_k$ be the graph induced by the first $k$ edges. Let $p(n)$ be probability that $H\_k$ is connected for all $k \in \{1,2,\dots,{n \choose 2}\}$.


As a corollary to a completely different problem I'm working on, and through a very round-about way, we were able to show that the answer for $p(n)$ is beautiful. Indeed, it is simply


$$\frac{2^{n-2}}{C\_{n-1}},$$
where $C\_{m}$ is the $m$th Catalan number.


I'd like to find a good combinatorial reason why this is the answer.


(This is the easiest case of a more general problem I'm working on. I do have one semi-combinatorial argument but unfortunately it doesn't generalize well.)


Any thoughts would be appreciated! Thanks!!



Probability of a graph procedure
Here's one. You can think of the graph construction process as gradually building a set $S$ of vertices that have been touched so far, beginning with a random two vertices. Let $S\_k$ be the set of the first $k$ vertices in this process.


Now $p(n)$ is exactly the probability that, after the first two vertices, each additional edge we select either has both endpoints in the current $S\_k$, or else crosses the cut between $S\_k$ and the rest of the graph. (In this case, the other endpoint becomes the next vertex to add to our set.)


Thus $p(n)$ is the probability that, at each set size $k$, conditioned on picking an edge that does not have both endpoints in $S\_k$, the edge selected crosses the cut. Well, the number of edges crossing the cut is exactly $k(n-k)$, and the number of edges entirely outside of $S\_k$ is exactly ${n-k \choose 2}$. Therefore the probability of picking an edge crossing the cut conditioned on one of these occurring is exactly
\begin{align}
 \frac{k(n-k)}{k(n-k) + {n-k \choose 2}}
 &= \frac{2k}{2k + n-k-1} \\
 &= \frac{2k}{n + k - 1}
\end{align}


As base cases, immediately $p(2) = 1$. For $n \geq 3$, we get
\begin{align}
 p(n) &= \prod\_{k=2}^{n-1} \frac{2k}{n-1 + k} \\
 &= 2^{n-2} \prod\_{k=2}^{n-1} \frac{k}{n-1 + k} \\
 &= 2^{n-2} \frac{1}{C\_{n-1}} .
\end{align}


