Probability of a graph procedure 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!!
 A: 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}
