This question is inspired by ["Number of collinear ways to fill a grid"](https://mathoverflow.net/questions/297385/number-of-collinear-ways-to-fill-a-grid) by Sebastien Palcoux and the comments of user44191 on [this earlier question of Palcoux's](https://mathoverflow.net/questions/297113/on-the-number-of-eulerian-orderings).


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"](https://mathoverflow.net/questions/297385/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](https://mathoverflow.net/questions/199342/probability-of-a-graph-procedure).



Counting "connected" edge orderings (shellings) of the complete graph
Write $\langle m\rangle\_i=m(m+1)\cdots (m+i-1)$. There are $\frac 12
n!$ ways to choose the order in which new vertices are attached (since
at the first step we attach two at once). There are $(n-1)!$ ways to
choose the vertex that each new vertex is attached to. Suppose we have
made these choices. Now there are $(n-2)!=\langle 1\rangle\_{n-2}$ ways
to choose the order in which we add the $n-2$ additional edges
incident to the last attached vertex. Then there are $\langle
n\rangle\_{n-3}$ ways to specify how to add the additional $n-3$
edges adjacent to the next-to-last attached vertex. Then there are
$\langle 2n-2\rangle\_{n-4}$ ways to specify how to add the additional
$n-4$ edges adjacent to the third-from-last attached
vertex. Continuing in this way shows that the total number of edge
orderings is
 $$ \frac 12n!\,(n-1)!\prod\_{i=0}^{n-3}
 \left\langle in-\binom{i+1}{2}+1\right\rangle\_{n-i-2} = \frac{2^n n! (n - 1)! \binom{n}{2}!}{4 (2n - 2)!} \text{ (see comments)}$$
Perhaps I have made a computational error, but I think the method is
correct.


I can also point out, though irrelevant to the solution, that you are
asking for the number of shellings of the complete graph, regarded as
a one-dimensional simplicial complex.


