# 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!!

• Typo, I think you mean $p(k)$ in the definition. The formula doesn't feel quite right, but should follow from Cayley's formula for labelled trees on $n$ vertices (in this process, when $n$ edges have been added we're asking for a tree plus an edge.) Mar 8, 2015 at 0:06
• Hmm.. I think I do mean $p(n)$. Starting with the empty graph on $n$ vertices we can add in ${n \choose 2}$ edges, one at a time, and ask whether the induced graphs were connected at every stage. Does that clear up the confusion? Or does something still seem amiss? Thanks! Mar 8, 2015 at 0:17
• I don't understand how the graphs can be connected at every stage. Do you mean that there is at most one non-singleton component? If so (and I guess that's it) then ignore my comment about Cayley's theorem! Mar 8, 2015 at 0:36
• Exactly. The way I phrased it was that $H_k$ is the graph ${induced}$ by the first $k$ edges, but maybe your way is more clear. Mar 8, 2015 at 0:38
• The total number of such permutations now forms the sequence oeis.org/A255886 in the OEIS. Mar 9, 2015 at 11:40

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}