This question is inspired by "Number of collinear ways to fill a grid" by Sebastien Palcoux and the comments of user44191 on this earlier question of Palcoux's.

Let $G=(V,E)$ be a graph. An **edge ordering** of $E$ (or $G$) is a bijection $\phi$ from $\{1,\dots,|E|\}$ to $E$. Let $G_k$ be the graph induced by the edge set $E_k=\{\phi(i)|1\leq i \leq k\}$. An edge ordering is **connected** if $G_k$ is connected for all $1\leq k\leq |E|$.

How many connected edge orderings are there for $G=K_n$, the complete graph on $n$ vertices?

Asymptotics would be fine, but I suspect there might be a nice closed-form expression:

For $K_{m,n}$ (the complete bipartite graph on sets of $m$ and $n$ vertices) the conjectured answer is $m!n!(mn)!/(m+n-1)!$, from "Number of collinear ways to fill a grid". This is because there's a bijection between connected edge orderings of $K_{m,n}$ and collinear $m\times n$ grid fillings (take the row and column sets to be the vertex sets of $K_{m,n}$ and grid squares to be the edges).

**edit**:

As Richard Stanley points out (and as I could have deduced if I'd looked at the earlier questions of Sebastien Palcoux), connected edge orderings of a graph are the same as **shellings** of that graph viewed as a 1D simplicial complex.

Here are SageMath implementations of user44191's recursion formula in the comments and Richard Stanley's formula in his answer (removing the factor of $n!/2$ coming from different orderings of the vertices).

```
def partialrecursionformula(m,n):
if [m,n] == [1,0]:
return 1
elif n<m-1 or m==0:
return 0
else:
i=n-1
return ((m*(m-1)/2 - i)*partialrecursionformula(m,i)
+ (m-1)*partialrecursionformula(m-1,i))
def recursionformula(m):
return partialrecursionformula(m,m*(m-1)/2)
def stanleyformula(m):
f = [rising_factorial(i*m - i*(i+1)/2 + 1, m-i-2) for i in range(m-2)]
return factorial(m-1)*prod(f)
```

Numerically, they agree at least up to $K_{8}$ (I am convinced that they both count the connected edge orderings correctly for all $n$, so this was just a check that there are no typos).

The sequence of the number of shellings of $K_n$ that reach the vertices in order thus begins 1, 1, 2, 48, 34560, 1383782400, 4914953551872000, 2256176006302688870400000, and it's easy to get more values with Richard Stanley's formula.

**edit 2**: Fedor Petrov points out in the comments that this question (phrased in terms of probabilities) has already been asked and answered here.

2more comments