Counting Shellings of Complete Bipartite Graphs and Trees
A shelling of a graph, viewed as an abstract simplicial complex that is pure of dimension 1, is an ordering of its edges such that every edge is adjacent to some other edges appeared previously. In this paper, we focus on complete bipartite graphs and trees. For complete bipartite graphs, we obtain an exact formula for their shelling numbers. And for trees, we relate their shelling numbers to linear extensions of tree posets and bound shelling numbers using vertex degrees and diameter.
\section{Introduction}
In combinatorial topology, shelling of a simplicial complex is a very useful and important notion that has been well-studied. 
\begin{definition}\label{def:shellingcomplex}
An (abstract) simplicial complex $\Delta$ is called \textit{pure} if all of its maximal simplicies have the same dimension. Given a finite (or countably infinite) simplicial complex $\Delta$ that is pure of dimension $d$, a \textit{shelling} is a total ordering of its maximal simplicies $C_1,C_2,\ldots$ such that for every $k>1$, $C_k\cap\left(\bigcup_{i=1}^{k-1}C_i\right)$ is pure of dimension $d-1$. A simplicial complex that admits a shelling is called \textit{shellable}.
\end{definition}
Shellable complexes enjoy many strong algebraic and topological properties. For example, a shellable complex is homotopy equivalent to a wedge sum of spheres, thus not allowing torsion in its homology. The study of shellability in its combinatorial aspects has turned out to be very fruitful as well. The arguably earliest notable result that polytopes are shellable is due to Brugesser and Mani (Section 8 of \cite{ziegler2012lectures}). Later on, Bjorner and Wachs developed theories on lexicographic
shellability (Section 12 of \cite{kozlov2007combinatorial}). In particular, shellable posets, which are posets whose order complexes are shellable, are studied and powerful notions such as $EL$-shellability and $CL$-shellability are invented. In a recent work, testing shellability is proved to be NP-complete \cite{goaoc2017shellability}.

As there is rich literature on shellability, little work has been done on counting the number of shellings for a specific simplicial complex. It is generally believed that if a simplicial complex is shellable, then it usually admits a lot of shellings, but no precise arguments are given.

In this paper, we investigate the problem of counting shellings, aiming to start a new line of research. We restrict our attentions to finite simplicial complexes that are pure of dimension 1, namely, undirected graphs, where interesting combinatorial arguments are already taking place. Let's first reformulate Definition~\ref{def:shellingcomplex} in the language of graph theory.
\begin{definition}[Graph Shelling]\label{def:shellinggraph}
Given an undirected graph $G=(V,E)$, where $V$ is the vertex set of $G$ and $E$ is the edge set of $G$, a \textit{shelling} of $G$ is a total ordering of the edge set $\sigma\in\S_E$, where $\S$ stands for symmetric group, such that $\sigma(1),\ldots,\sigma(k)$ form a connected subgraph of $G$ for all $k=1,\ldots,|E|$.
\end{definition}
We will adopt the following notation throughout the paper.
\begin{definition}
For a graph $G$, let $F(G)$ denote the number of shellings of $G$.
\end{definition}
Clearly, a graph admits a shelling if and only if it is connected, which is equivalent to $F(G)>0$. A few results are already known.
\begin{theorem}[\cite{MO297411}]
Let $K_n$ be the complete graph on $n$ vertices. Then
$$F(K_n)=\frac{2^{n-2}}{C_{n-1}}\binom{n}{2}!$$
where $C_{n-1}=\binom{2n-2}{n-1}/n$ is the $(n-1)^{th}$ Catalan number.
\end{theorem}

As an overview for the paper, in Section~\ref{sec:cbg}, we will give an explicit formula for the number of shellings of complete bipartite graphs, resolving a MathOverflow question \cite{MO297385}; in Section~\ref{sec:trees}, we will provide methods to compute the number of shellings of trees and obtain some upper and lower bounds for them.
\section{Complete Bipartite Graphs}\label{sec:cbg}
Denote $K_{m,n}$ as the complete bipartite graph with part sizes $m$ and $n$. The following is our main theorem.
\begin{theorem}\label{thm:bipartite}
$$F(K_{m,n})=\frac{m!n!(mn)!}{(m+n-1)!}.$$
\end{theorem}
The formula in Theorem~\ref{thm:bipartite} is conjectured in the MathOverflow post \cite{MO297385}. Partial progress has been made. In particular, Lemma~\ref{lem:bipartiteStanley}, given by Richard Stanley, serves as an important tool for our computation.

\begin{lemma}\label{lem:bipartiteStanley}
$F(K_{m,n})$ is equal to the following expression:
$$m!n!(mn-1)!\sum_{\alpha}\frac{b_{1}b_{2}\cdots b_{m+n-2}}{b_{m+n-2}(b_{m+n-2}+b_{m+n-3})\cdots (b_{m+n-2}+b_{m+n-3}+\ldots+b_1)},$$
where the sum is over all sequences $\alpha = (a_1,a_2,\ldots,a_{m+n-2})$ of $(m-1)$ 0's and $(n-1)$ 1's, and
$$b_{i} = 1 + |\{1\leq j\leq i: a_j \neq a_i\}|.$$
\end{lemma}
\begin{proof}
Let $\sigma$ be a shelling of $K_{m,n}$. In each part of $K_{m,n}$, consider the order of the appearance of the vertices. Here, we say that vertex $v$ appears in $\sigma$ at time $t$ if $t$ is the first index such that $v\in \sigma(t)$. There are $m!$ ways to choose such order in the part of size $m$ and $n!$ ways in the part of size $n$. Fix the order of vertex appearance in each part to be $(u_0,u_1,\ldots,u_{m-1}), (v_0,v_1,\ldots,v_{n-1})$, respectively.

Consider a fixed order of appearance of all $(m+n)$ vertices $w = w_{-1}w_0\ldots w_{m+n-2}.$ Note that $\sigma(1)$ must be the edge $e_0=(u_0,v_0)$, so $\{w_{-1},w_0\} = \{u_0,v_0\}.$ For $1\leq i\leq m+n-2$, define 
$$a_{i} = 
\begin{cases}
0, & \text{ if } w_{i} = u_j \text{ for some }j, \\
1, & \text{ if } w_{i} = v_k \text{ for some }k,
\end{cases}$$
and 
$$b_i = 1 + |\{1\leq j\leq i: a_j \neq a_i\}|.$$
Now, for each $w_i$ ($i\geq 1$), consider the first edge $e_i$ incident to $w_i$ in $\sigma$. This edge must be of the form $(w_i,w_j)$ where $j<i$ and $w_i, w_j$ are in different parts of $K_{m,n}$. There are $b_{i}$ choices for this edge. Thus, there are $b_1b_2\cdots b_{m+n-2}$ ways to choose $e_1,e_2,\ldots,e_{m+n-2}.$

We further fix the edges $e_0,e_1,\ldots,e_{m+n-2}$. Note that the rest of the $b_{m+n-2}$ edges incident to $w_{m+n-2}$ must appear after $e_{m+n-2}$ in $\sigma$, so there are $(b_{m+n-2}-1)!$ ways to arrange these edges. After making this arrangement, the edges which are incident to $w_{m+n-3}$ and not yet arranged must appear after $e_{m+n-3}$, so there are
$$(b_{m+n-2}+1)(b_{m+n-2}+2)\cdots (b_{m+n-2}+b_{m+n-3}+1) = \frac{(b_{m+n-2}+b_{m+n-3}+1)!}{b_{m+n-2}!}$$
ways to arrange them (since there are already $b_{m+n-2}$ edges arranged after $e_{m+n-3}$). Similarly, for each $i$, after making the arrangement of all edges incident to vertices appearing after $w_i$, there are 
$$\frac{(b_{m+n-2}+b_{m+n-3}+\ldots + b_i + 1)!}{(b_{m+n-2}+b_{m+n-3}+\ldots + b_{i+1})!}$$
ways to arrange all the edges which are incident to $w_i$ and not yet arranged. Therefore, after fixing $e_0,e_1,\ldots,e_{m+n-2}$, the number of shellings is
$$\prod_{i=1}^{m+n-2}\frac{(b_{m+n-2}+\ldots + b_i + 1)!}{(b_{m+n-2}+\ldots + b_{i+1})!} = \frac{(mn-1)!}{b_{m+n-2}(b_{m+n-2}+b_{m+n-3})\cdots (b_{m+n-2}+\ldots+b_1)}.$$

Combining all discussions above, we obtain Lemma~\ref{lem:bipartiteStanley}.
\end{proof}

We first prove a few lemmas which are essential to Theorem~\ref{thm:bipartite}. These lemmas involve binomial coefficients whose entries are not necessarily integers. For this reason, in the rest of this section, we will use the generalized binomial coefficient
$$\binom{x}{y} = \frac{\Gamma(x+1)}{\Gamma(y+1)\Gamma(x-y+1)},$$
where $\Gamma$ is the Gamma function that extends the factorial function.
In particular, if $y$ is a positive integer,
$$\binom{x}{y} = \frac{x(x-1)\cdots (x-y+1)}{y!}.$$
\begin{lemma}\label{lem:story}
For positive integers $x,y$ and positive real numbers $z,w$ such that $w-z\geq x$ is a postive integer,
$$\sum_{j=x}^{w-z}\binom{j}{y}\binom{w-j}{z}=\sum_{i=\max\{0,x+y+z-w\}}^y \binom{x}{i}\binom{w-x+1}{z+y-i+1}.$$
\end{lemma}
\begin{proof}
We first prove this lemma assuming that $z,w$ are both integers. Consider the following problem: we want to arrange $(y+z+1)$ letter A's in $(w+1)$ positions, such that each position has at most one A and there are at most $y$ A's in the first $x$ positions. The number of such arrangements is
$$\sum_{i=0}^y \binom{x}{i}\binom{w-x+1}{z+y-i+1} = \sum_{i=\max\{0,x+y+z-w\}}^y \binom{x}{i}\binom{w-x+1}{z+y-i+1}$$
by considering the number of A's in the first $x$ positions.

On the other hand, consider the position of the $(y+1)^{th}$ A. It must be at some position $p>x$. For a fixed $p$, there are $\binom{p-1}{y}$ ways to arrange the first $y$ A's and $\binom{w-p+1}{z}$ ways to arrange the last $z$ A's, so the total number of such arrangements is 
$$\sum_{p=x+1}^{w-z+1}\binom{p-1}{y}\binom{w-p+1}{z} = \sum_{j=x}^{w-z}\binom{j}{y}\binom{w-j}{z}.$$
Thus, Lemma~\ref{lem:story} follows under additional assumption.

For the general case, we fix $z' = w-z \in \mathbb{N}$. Lemma~\ref{lem:story} is equivalent to
\begin{equation}\label{eq:story}
\sum_{j=x}^{z'}\binom{j}{y}\binom{w-j}{z'-j}=\sum_{i=\max\{0,x+y-z'\}}^y \binom{x}{i}\binom{w-x+1}{z'-x-y+i}.
\end{equation}
Both sides of Equation~\eqref{eq:story} are polynomials in $w$ of degree at most $z'$. From our previous discussion, every positive integer greater than $z'$ is a root of ~\eqref{eq:story}. Thus, the two sides of ~\eqref{eq:story} agree as polynomials in $w$ and the proof is complete.
\end{proof}

Lemma~\ref{lem:story} serves to prove the following lemma, which will be crucial in calculating the sum in Lemma~\ref{lem:bipartiteStanley}.
\begin{lemma}\label{lem:binomialComputation}
For positive integers $k<n$ and $s<m+n-k-1$,
\begin{equation}\label{eq:lemma}
\begin{split}
&\sum_{t=s+1}^{m+n-k-1}(t-n+k+1)(t+2)(t+3)\cdots(t+k)\binom{\frac{mn}{n-k}+n-k-t-2}{\frac{mk}{n-k}-1} \\
=&\frac{m}{m+n-k}(s+2)(s+3)\cdots(s+k+1)\binom{\frac{mn}{n-k}+n-k-s-2}{\frac{mk}{n-k}},
\end{split}
\end{equation}
where general binomial coefficients are used.
\end{lemma}
\begin{proof}
First, note that
$$(t-n+k+1)(t+2)(t+3)\cdots (t+k) = k!\bigg[\binom{t+k}{k} +\frac{k-n}{k}\binom{t+k}{k-1}\bigg].$$
We shall split the sum in the left hand side of $(\ref{eq:lemma})$ based on the equation above.
Applying Lemma~\ref{lem:story} with replacements $x=s+k+1$, $y=k$, $z=\frac{mk}{n-k}-1$, $w=\frac{mn}{n-k}+n-2$ (notice that $w-z = m+n-1$ is a positive integer), we obtain
$$\sum_{j = s+k+1}^{m+n-1}\binom{j}{k}\binom{\frac{mn}{n-k}+n-2-j}{\frac{mk}{n-k}-1} = \sum_{i=i_0}^{k} \binom{s+k+1}{i}\binom{\frac{mn}{n-k}+n-k-s-2}{\frac{mk}{n-k}+k-i},$$
where $i_0 = \max\{0, s+2k+2-m-n\}.$
Writing $t=j-k$, we have
$$\sum_{t = s+1}^{m+n-k-1}\binom{t+k}{k}\binom{\frac{mn}{n-k}+n-k-t-2}{\frac{mk}{n-k}-1} = \sum_{i=i_0}^{k} \binom{s+k+1}{i}\binom{\frac{mn}{n-k}+n-k-s-2}{\frac{mk}{n-k}+k-i}.$$
Similarly, replacing $x=s+k+1$, $y=k-1$, $z=\frac{mk}{n-k}-1$, $w=\frac{mn}{n-k}+n-2$ in Lemma~\ref{lem:story},
\begin{align*}
\sum_{t=s+1}^{m+n-k-1}\binom{t+k}{k-1}\binom{\frac{mn}{n-k}+n-k-t-2}{\frac{mk}{n-k}-1} &= \sum_{i=i_1}^{k-1} \binom{s+k+1}{i}\binom{\frac{mn}{n-k}+n-k-s-2}{\frac{mk}{n-k}+k-i-1}\\
&=\sum_{i=i_1+1}^{k} \binom{s+k+1}{i-1}\binom{\frac{mn}{n-k}+n-k-s-2}{\frac{mk}{n-k}+k-i},
\end{align*}
where $i_1 = \max\{0, s+2k+1-m-n\}.$ Therefore, the left hand side of (\ref{eq:lemma})

\begin{equation*}
\begin{split}
&\frac{1}{k!}\sum_{t=s+1}^{m+n-k-1}(t-n+k+1)(t+2)(t+3)\cdots(t+k)\binom{\frac{mn}{n-k}+n-k-t-2}{\frac{mk}{n-k}-1} \\
=& \sum_{i=i_0}^{k} \binom{s+k+1}{i}\binom{\frac{mn}{n-k}+n-k-s-2}{\frac{mk}{n-k}+k-i}+\frac{k-n}{k}\sum_{i=i_1+1}^{k} \binom{s+k+1}{i-1}\binom{\frac{mn}{n-k}+n-k-s-2}{\frac{mk}{n-k}+k-i}.
\end{split}
\end{equation*}

We claim that the following identity (\ref{eq:inductionLemma}) holds for all $i_0\leq \ell\leq k$.
\begin{equation}\label{eq:inductionLemma}
\begin{split}
& \sum_{i=i_0}^{\ell} \binom{s+k+1}{i}\binom{\frac{mn}{n-k}+n-k-s-2}{\frac{mk}{n-k}+k-i}+\frac{k-n}{k}\sum_{i=i_1+1}^{\ell} \binom{s+k+1}{i-1}\binom{\frac{mn}{n-k}+n-k-s-2}{\frac{mk}{n-k}+k-i} \\
=&\frac{\frac{mk}{n-k}+k-\ell}{\frac{mk}{n-k}+k}\binom{s+k+1}{\ell}\binom{\frac{mn}{n-k}+n-k-s-2}{\frac{mk}{n-k}+k-\ell}.
\end{split}
\end{equation}


There are two cases: $i_0=0$ and $i_0>0$.

\noindent\textbf{Case 1.} $i_0 = i_1 = 0.$ 

In this case, the left hand side of (\ref{eq:inductionLemma}) is
\begin{equation*}
\binom{\frac{mn}{n-k}+n-k-s-2}{\frac{mk}{n-k}+k}+\sum_{i=1}^\ell \bigg[\binom{s+k+1}{i}+\frac{k-n}{k}\binom{s+k+1}{i-1}\bigg]\binom{\frac{mn}{n-k}+n-k-s-2}{\frac{mk}{n-k}+k-i}.
\end{equation*}

Induct on $\ell$. When $\ell=0$, both sides of (\ref{eq:inductionLemma}) are equal to $\binom{\frac{mn}{n-k}+n-k-s-2}{\frac{mk}{n-k}+k}.$ Assume that (\ref{eq:inductionLemma}) holds for $\ell-1$ and consider $\ell$ case. Then, the formula above becomes
\begin{align*}
& \bigg[\binom{s+k+1}{\ell}+\frac{k-n}{k}\binom{s+k+1}{\ell-1}\bigg]\binom{\frac{mn}{n-k}+n-k-s-2}{\frac{mk}{n-k}+k-\ell} + \\ 
&\qquad\frac{\frac{mk}{n-k}+k-\ell+1}{\frac{mk}{n-k}+k}\binom{s+k+1}{\ell-1}\binom{\frac{mn}{n-k}+n-k-s-2}{\frac{mk}{n-k}+k-\ell+1} \\
=&\bigg[\binom{s+k+1}{\ell}+\frac{k-n}{k}\cdot\frac{\ell}{s+k+2-\ell}\binom{s+k+1}{\ell}\bigg]\binom{\frac{mn}{n-k}+n-k-s-2}{\frac{mk}{n-k}+k-\ell} + \\
&\ \frac{\frac{mk}{n-k}+k-\ell+1}{\frac{mk}{n-k}+k}\frac{\ell}{s+k+2-\ell}\binom{s+k+1}{\ell}\frac{m+n+\ell-2k-s-2}{\frac{mk}{n-k}+k-\ell+1}\binom{\frac{mn}{n-k}+n-k-s-2}{\frac{mk}{n-k}+k-\ell} \\
=& \left(1+\frac{(k-n)\ell}{k(s+k+2-\ell)}+ \frac{(m+n+\ell-2k-s-2)\ell}{(\frac{mk}{n-k}+k)(s+k+2-\ell)}\right)\binom{s+k+1}{\ell}\binom{\frac{mn}{n-k}+n-k-s-2}{\frac{mk}{n-k}+k-\ell} \\
=& \frac{\frac{mk}{n-k}+k-\ell}{\frac{mk}{n-k}+k}\binom{s+k+1}{\ell}\binom{\frac{mn}{n-k}+n-k-s-2}{\frac{mk}{n-k}+k-\ell}.
\end{align*}
Thus, (\ref{eq:inductionLemma}) follows by induction.

\noindent\textbf{Case 2.}
$i_0 = s+2k+2-m-n > 0$ and $i_1 = i_0 - 1.$ 

We can simplify the left hand side of (\ref{eq:inductionLemma}) as
\begin{equation*}
\sum_{i=i_0}^{\ell} \bigg[\binom{s+k+1}{i}+\frac{k-n}{k}\binom{s+k+1}{i-1}\bigg]\binom{\frac{mn}{n-k}+n-k-s-2}{\frac{mk}{n-k}+k-i}.
\end{equation*}
Induct on $\ell$. When $\ell = i_0$,
\begin{align*}
&\bigg[\binom{s+k+1}{i_0}+\frac{k-n}{k}\cdot \frac{i_0}{s+k+2-i_0}\binom{s+k+1}{i_0}\bigg]\binom{\frac{mn}{n-k}+n-k-s-2}{\frac{mk}{n-k}+k-i_0} \\
=& \frac{\frac{mk}{n-k}+k-i_0}{\frac{mk}{n-k}+k}\binom{s+k+1}{i_0}\binom{\frac{mn}{n-k}+n-k-s-2}{\frac{mk}{n-k}+k-i_0},
\end{align*}
as desired.
The inductive step $(\ell-1) \Rightarrow \ell$ holds by the same calculation as the previous case $i_0=0$.
\begin{comment}
\begin{align*}
(\ref{eq:simplification2}) =& \bigg[\binom{s+k+1}{l}+\frac{k-n}{k}\binom{s+k+1}{l-1}\bigg]\binom{\frac{mn}{n-k}+n-k-s-2}{\frac{mk}{n-k}+k-l} + \\ 
&\qquad\frac{\frac{mk}{n-k}+k-l+1}{\frac{mk}{n-k}+k}\binom{s+k+1}{l-1}\binom{\frac{mn}{n-k}+n-k-s-2}{\frac{mk}{n-k}+k-l+1} \\
=& \frac{\frac{mk}{n-k}+k-l}{\frac{mk}{n-k}+k}\binom{s+k+1}{l}\binom{\frac{mn}{n-k}+n-k-s-2}{\frac{mk}{n-k}+k-l}.
\end{align*}
\end{comment}
Thus, the claim follows by induction.


In particular, when $\ell=k$, (\ref{eq:inductionLemma}) becomes
\begin{equation*}
\begin{split}
& \sum_{i=i_0}^{k} \binom{s+k+1}{i}\binom{\frac{mn}{n-k}+n-k-s-2}{\frac{mk}{n-k}+k-i}+\frac{k-n}{k}\sum_{i=i_1+1}^{k} \binom{s+k+1}{i-1}\binom{\frac{mn}{n-k}+n-k-s-2}{\frac{mk}{n-k}+k-i} \\
=&\frac{1}{k!}\cdot\frac{m}{m+n-k}(s+2)(s+3)\cdots(s+k+1)\binom{\frac{mn}{n-k}+n-k-s-2}{\frac{mk}{n-k}}.
\end{split}
\end{equation*}
Therefore, the proof of this lemma is complete.
\end{proof}

Now we are ready to prove Theorem~\ref{thm:bipartite}.
\begin{proof}[Proof of Theorem~\ref{thm:bipartite}]
According to Lemma~\ref{lem:bipartiteStanley}, it suffices to show that 
\begin{equation*}
(mn-1)!\sum_{\alpha}\frac{b_{1}b_{2}\cdots b_{m+n-2}}{b_{m+n-2}(b_{m+n-2}+b_{m+n-3})\cdots (b_{m+n-2}+b_{m+n-3}+\ldots+b_1)} = \frac{(mn)!}{(m+n-1)!}.
\end{equation*}
where the sum is over all sequences $\alpha=(a_1,a_2,\ldots,a_{m+n-2})$ consisting of $(m-1)$ 0's and $(n-1)$ 1's. Suppose $a_{r_1}=a_{r_2}=\ldots=a_{r_{n-1}} = 1$ where $1\leq r_1<r_2<\ldots<r_{n-1}\leq m+n-2$. Denote $r_0 = 0$. Then for $k=1,2,\ldots,n-1$,
\begin{comment}
\begin{align*}
b_1 = b_2 = \ldots = b_{r_1-1} = 1,&\  b_{r_1} = r_1,\\
\vdots \qquad & \\
b_{r_{k-1}+1} = \ldots = b_{r_k-1} = k,&\ b_{r_k} = r_{k}-k+1,\\
\vdots \qquad & \\
b_{r_{n-1}+1} = \ldots = b_{m+n-2} = n.
\end{align*}
\end{comment}
$$b_{r_{k-1}+1} = b_{r_{k-1}+2} = \cdots = b_{r_k-1} = k, b_{r_k} = r_{k}-k+1$$
and
$$b_{r_{n-1}+1} = \cdots = b_{m+n-2} = n.$$
Therefore,
\begin{equation*}
\prod_{i=1}^{m+n-2}b_i = n^{m+n-2-r_{n-1}}\prod_{j=1}^{n-1} (r_j -j+1) j^{r_{j}-r_{j-1}-1}.
\end{equation*}

For $1\leq i\leq m+n-2$, write $c_i = b_{m+n-2}+\ldots + b_{i}$, then
$$c_{m+n-2} = n, c_{m+n-3} = 2n, \ldots, c_{r_{n-1}+1} = mn+n(n-2-r_{n-1})$$
$$\implies c_{m+n-2}c_{m+n-3}\cdots c_{r_{n-1}+1} = n^{m+n-2-r_{n-1}}\Gamma(m+n-1-r_{n-1})$$
\begin{comment}
$$c_{r_{n-1}} = mn +(n-1)(n-2-r_{n-1}),\ldots, c_{r_{n-2}+1} = mn+(n-1)(n-3-r_{n-2}),$$
\begin{align*}
\implies c_{r_{n-1}}\cdots c_{r_{n-2}+1} &= (n-1)^{r_{n-1}-r_{n-2}}\prod_{i=r_{n-2}+1}^{r_{n-1}} (\frac{mn}{n-1}+n-2-i) \\
&= (n-1)^{r_{n-1}-r_{n-2}}\frac{\Gamma(\frac{mn}{n-1}+n-2-r_{n-2})}{\Gamma(\frac{mn}{n-1}+n-2-r_{n-1})}.
\end{align*}
\end{comment}
For $k=1,2,\ldots,n-1,$ we have
$$c_{r_{k}} = mn+k(k-1-r_k),\ldots, c_{r_{k-1}+1} = mn+k(k-2-r_{k-1})$$
\begin{align*}
\implies c_{r_{k}}\cdots c_{r_{k-1}+1} &= k^{r_{k}-r_{k-1}}\prod_{i=r_{k-1}+1}^{r_{k}} (\frac{mn}{k}+k-1-i) \\
&= k^{r_{k}-r_{k-1}}\frac{\Gamma(\frac{mn}{k}+k-1-r_{k-1})}{\Gamma(\frac{mn}{k}+k-1-r_{k})}.
\end{align*}
\begin{comment}
$$c_{r_1} = mn-r_1,\ldots, c_1 = mn-1.$$
$$\implies c_{r_1}\cdots c_1 = \frac{\Gamma(mn)}{\Gamma(mn-r_1)}.$$
\end{comment}

Denote $r_n = m+n-2$, we have
\begin{equation*}
\begin{split}
\prod_{i=1}^{m+n-2}c_i &= \prod_{j=1}^{n} j^{r_{j}-r_{j-1}}\frac{\Gamma(\frac{mn}{j}+j-1-r_{j-1})}{\Gamma(\frac{mn}{j}+j-1-r_{j})} \\
&=(mn-1)!\bigg(\prod_{j=1}^{n} j^{r_{j}-r_{j-1}}\bigg)\bigg(\prod_{k=1}^{n-1}\frac{\Gamma(\frac{mn}{k+1}+k-r_{k})}{\Gamma(\frac{mn}{k}+k-1-r_{k})}\bigg)
\end{split}
\end{equation*}
Comparing the product of $b_i$'s and $c_i$'s, we obtain
$$(mn-1)!\prod_{i=1}^{m+n-2}\frac{b_i}{c_i} = \frac{1}{(n-1)!}\prod_{k=1}^{n-1}(r_k-k+1)\frac{\Gamma(\frac{mn}{k}+k-1-r_{k})}{\Gamma(\frac{mn}{k+1}+k-r_{k})}.$$
\begin{align*}
\implies (mn-1)!\sum_{\alpha}\prod_{i=1}^{m+n-2}\frac{b_i}{c_i} =& \frac{1}{(n-1)!}\sum_{1\leq r_1<\ldots<r_{n-1}\leq m+n-2}\prod_{j=1}^{n-1}(r_j-j+1)\frac{\Gamma(\frac{mn}{j}+j-1-r_{j})}{\Gamma(\frac{mn}{j+1}+j-r_{j})} \\
=& \frac{1}{(n-1)!}\sum_{1\leq r_1<\ldots<r_{n-1}\leq m+n-2}\prod_{j=1}^{n-1}R_j,
\end{align*}
where $R_j = (r_j-j+1)\frac{\Gamma(\frac{mn}{j}+j-1-r_{j})}{\Gamma(\frac{mn}{j+1}+j-r_{j})}.$

We claim that the sum 
\begin{equation}\label{eq:inductionTheorem}
\begin{split}
&\frac{1}{(n-1)!}\sum_{1\leq r_1<\ldots<r_{n-1}\leq m+n-2}\prod_{j=1}^{n-1}R_j \\
=&\frac{(m+k)!\Gamma(\frac{m(n-k)}{k})}{(m+n-1)!k!(n-k-1)!}\sum_{1\leq r_1<\ldots<r_{k}\leq m+k-1}(r_k-k+1)\frac{(r_k+n-k)!}{(r_k+1)!}\binom{\frac{mn}{k}+k-2-r_k}{\frac{m(n-k)}{k}-1}\prod_{j=1}^{k-1}R_j
\end{split}
\end{equation}
for all $1\leq k\leq n-1$. 

To prove this claim, we reversely induct on $k$. When $k=n-1$, the right hand side of (\ref{eq:inductionTheorem})
\begin{align*}
&\frac{\Gamma(\frac{m}{n-1})}{(n-1)!}\sum_{1\leq r_1<\ldots<r_{n-1}\leq m+n-2}(r_{n-1}-n+2)\frac{\Gamma(\frac{mn}{n-1}+n-2-r_{n-1})}{\Gamma(\frac{m}{n-1})\Gamma(m+n-1-r_{n-1})}\prod_{j=1}^{n-2}R_j \\
=& \frac{1}{(n-1)!}\sum_{1\leq r_1<\ldots<r_{n-1}\leq m+n-2}\prod_{j=1}^{n-1}R_j,
\end{align*}
as desired.

Assume that the claim holds for $k+1$, then the left hand side of (\ref{eq:inductionTheorem}) becomes
\begin{equation}\label{eq:inductionStep1}
\frac{(m+k+1)!\Gamma(\frac{m(n-k-1)}{k+1})}{(m+n-1)!(k+1)!(n-k-2)!}\sum_{1\leq r_1<\ldots<r_{k+1}\leq m+k}(r_{k+1}-k)\frac{(r_{k+1}+n-k-1)!}{(r_{k+1}+1)!}\binom{\frac{mn}{k+1}+k-1-r_{k+1}}{\frac{m(n-k-1)}{k+1}-1}\prod_{j=1}^{k}R_j
\end{equation}
Setting $t=r_{k+1},s= r_{k}, k\rightarrow n-k-1$ in Lemma~\ref{lem:binomialComputation}, we have
\begin{align*}
&\sum_{1\leq r_1<\ldots<r_{k+1}\leq m+k}(r_{k+1}-k)\frac{(r_{k+1}+n-k-1)!}{(r_{k+1}+1)!}\binom{\frac{mn}{k+1}+k-1-r_{k+1}}{\frac{m(n-k-1)}{k+1}-1}\prod_{j=1}^{k}R_j \\
=& \sum_{1\leq r_1<\ldots<r_k\leq m+k-1}\bigg[\bigg(\prod_{j=1}^{k}R_j\bigg)\sum_{r_{k+1} = r_k+1}^{m+k}(r_{k+1}-k)\frac{(r_{k+1}+n-k-1)!}{(r_{k+1}+1)!}\binom{\frac{mn}{k+1}+k-1-r_{k+1}}{\frac{m(n-k-1)}{k+1}-1}\bigg] \\
=& \sum_{1\leq r_1<\ldots<r_k\leq m+k-1}\bigg[\bigg(\prod_{j=1}^{k}R_j\bigg)\frac{m}{m+k+1}(r_k+2)(r_k+3)\cdots(r_k+n-k)\binom{\frac{mn}{k+1}+k-r_k-1}{\frac{m(n-k-1)}{k+1}}\bigg] \\
=& \sum_{1\leq r_1<\ldots<r_k\leq m+k-1}\frac{m}{m+k+1}\cdot\frac{(r_k+n-k)!}{(r_k+1)!}\binom{\frac{mn}{k+1}+k-r_k-1}{\frac{m(n-k-1)}{k+1}}\prod_{j=1}^{k}R_j.
\end{align*}
Thus,
\begin{align*}
(\ref{eq:inductionStep1}) &= \frac{(m+k+1)!\Gamma(\frac{m(n-k-1)}{k+1})}{(m+n-1)!(k+1)!(n-k-2)!}\sum_{1\leq r_1<\ldots<r_k\leq m+k-1}\frac{m(r_k+n-k)!}{(m+k+1)(r_k+1)!}\binom{\frac{mn}{k+1}+k-r_k-1}{\frac{m(n-k-1)}{k+1}}\prod_{j=1}^{k}R_j \\
&=\frac{(m+k)!\Gamma(\frac{m(n-k-1)}{k+1})}{(m+n-1)!(k+1)!(n-k-2)!} \sum_{1\leq r_1<\ldots<r_k\leq m+k-1}\frac{m(r_k+n-k)!}{(r_k+1)!}\frac{\Gamma(\frac{mn}{k+1}+k-r_k)}{\Gamma(\frac{m(n-k-1)}{k+1}+1)\Gamma(m+k-r_k)}\prod_{j=1}^{k}R_j \\
&=\frac{(m+k)!}{(m+n-1)!k!(n-k-1)!}\cdot \\
&\qquad \sum_{1\leq r_1<\ldots<r_k\leq m+k-1}\frac{(r_k+n-k)!}{(r_k+1)!}\frac{\Gamma(\frac{mn}{k+1}+k-r_k)}{\Gamma(m+k-r_k)} (r_k-k+1)\frac{\Gamma(\frac{mn}{k}+k-1-r_{k})}{\Gamma(\frac{mn}{k+1}+k-r_{k})}\prod_{j=1}^{k-1}R_j\\
&=\frac{(m+k)!\Gamma(\frac{m(n-k)}{k})}{(m+n-1)!k!(n-k-1)!}\sum_{1\leq r_1<\ldots<r_{k}\leq m+k-1}(r_k-k+1)\frac{(r_k+n-k)!}{(r_k+1)!}\binom{\frac{mn}{k}+k-2-r_k}{\frac{m(n-k)}{k}-1}\prod_{j=1}^{k-1}R_j.
\end{align*}
and the claim follows by (reverse) induction.

In particular, when $k=1$, $(\ref{eq:inductionTheorem})$ becomes
\begin{equation*}
\frac{(m+1)!(mn-m-1)!}{(m+n-1)!(n-2)!}\sum_{r_1=1}^m r_1\frac{(r_1+n-1)!}{(r_1+1)!}\binom{mn-r_1-1}{mn-m-1}.
\end{equation*}
Again, setting $t=r_1, s=0, k=n-1$ in Lemma~\ref{lem:binomialComputation},
$$\sum_{r_1=1}^m r_1\frac{(r_1+n-1)!}{(r_1+1)!}\binom{mn-r_1-1}{mn-m-1} = \frac{m}{m+1}\cdot n!\binom{mn-1}{mn-m}.$$
Therefore,
\begin{align*}
(\ref{eq:inductionTheorem}) &= \frac{(m+1)!(mn-m-1)!}{(m+n-1)!(n-2)!}\cdot\frac{m}{m+1}\cdot n!\binom{mn-1}{mn-m} \\
&= \frac{(mn)!}{(m+n-1)!}.
\end{align*}
Therefore, the proof of Theorem~\ref{thm:bipartite} is complete.
\end{proof}

\section{Trees}\label{sec:trees}
\subsection{Tree Shelling Number Computation}

\

Trees are one of the most fundamental type of graphs. However, unlike the complete bipartite graph case, there is no simple formula for tree shelling numbers. The goal of this section is to give a relatively easy method to compute the number of shellings of a tree.

Throughout this section, let $T$ be a tree with $n$ vertices and $n-1$ edges. We first focus on computing the number of shellings of rooted trees, whose definition is given below.

\begin{definition}\label{def:shellingOfRootedTree}
Let $v$ be a vertex of $T$. The rooted tree induced by $T$ and rooted at $v$ is denoted as $T_v$. A \textit{shelling of rooted tree} $T_v$ is a shelling $\sigma$ of $T$ such that $\sigma(1)$ is an edge incident to $v$.
\end{definition}

The following definitions are used to efficiently describe structures in a (rooted) tree.


\begin{definition}\label{def:parent}
Let $T_v$ be a tree rooted at vertex $v$.  We say a vertex $u$ is a \textit{parent} of vertex $w$ (and $w$ is a \textit{child} of $u$) if $(w,u)$ is an edge and $u$ lies closer to the root than $w$. A \textit{descending path} from $u$ to $w$ in the rooted tree $T_v$ is a structure
$$u-v_1-v_2-\cdots -v_r-w$$
where each vertex is a parent of the subsequent vertex. We say $u$ is an \textit{ancestor} of $w$ (and $w$ is a \textit{descendant} of $u$) if there exists a descending path from $u$ to $w$.
\end{definition}

\begin{definition}\label{def:rootedSubtree}
Let $u,v\in T.$ The (rooted)\textit{ subtree of $T_v$ rooted at $u$}, denoted as $T_v(u)$, is a subgraph of $T$ rooted at $u$ and induced by the set of vertices
$$\{w\in T: w \text{ is a descendant of } u \text{ in }T_v\}.$$
See Figure~\ref{fig:definition} for an example.
\end{definition}
\begin{figure}[h]
\begin{tikzpicture}[scale=1]
\draw (2,-1)--(0,0)--(-2,-1);
\draw (0,0)--(0.5,-1);
\draw (-1.5,-2)--(-2,-1)--(-2.5,-2);
\draw (0.5,-2)--(0.5,-1)--(1.5,-2);
\draw (-0.5,-2)--(0.5,-1);
\draw (-3,-3)--(-2.5,-2)--(-2,-3);
\draw (-1.5,-3)--(-1.5,-2);
\draw (0,-3)--(0.5,-2)--(1,-3);
\draw (1.75,-3)--(1.5,-2);

\node at (0,0){$\bullet$};
\node at (-2,-1){$\bullet$};
\node at (2,-1){$\bullet$};
\node at (0.5,-1){$\bullet$};
\node at (-2.5,-2){$\bullet$};
\node at (-1.5,-2){$\bullet$};
\node at (0.5,-2){$\bullet$};
\node at (-0.5,-2){$\bullet$};
\node at (1.5,-2){$\bullet$};
\node at (-3,-3){$\bullet$};
\node at (-2,-3){$\bullet$};
\node at (-1.5,-3){$\bullet$};
\node at (1,-3){$\bullet$};
\node at (0,-3){$\bullet$};
\node at (1.75,-3){$\bullet$};

\draw (0,0) node[above]{$v$};
\draw (-2,-1) node[above]{$u$};
\draw (-2.2,-2.2) ellipse (1.2 and 1.7);
\draw (-3.1,-1) node[left]{$T_v(u)$};
\end{tikzpicture}
\caption{Definition of $T_v(u)$.}
\label{fig:definition}
\end{figure}

For a tree $T$, the edge set of $T$ is denoted as $E(T)$. The vertex set of $T$ is denoted as $V(T)$, or $T$ for simplicity. Accordingly, $|T|$ is the number of vertices in $T$. The same notations are used for rooted trees.

The following proposition provides a way to calculate the number of shellings of a rooted tree $T_v$ based on the size of its rooted subtrees.

\begin{proposition}\label{prop:rootedTreeCounting}
$$F(T_v) = \frac{n!}{\prod_{u\in T} |T_v(u)|}.$$
\end{proposition}
\begin{proof}
The proposition holds for $n=2$ by regular check. Assume that it holds for $n-1$ and consider a tree $T$ with $n$ vertices.

Suppose the neighbors of $v$ are $u_1, u_2,\ldots,u_r.$ For $1\leq i\leq r,$ define $T^{(i)}$ to be the tree $T_{v}(u_i)$ with an additional edge $(u_i,v)$. Given fixed shellings $\sigma_i$ of $T_v^{(i)}$ for all $1\leq i\leq r$, we can construct shellings of $T_v$ by merging $\sigma_i$'s together while preserving the order of each $\sigma_i$. Every shelling of $T_v$ can be uniquely constructed in this way. Therefore,
$$F(T_v) = \binom{|E(T)|}{|E(T^{(1)})|,|E(T^{(2)})|,\ldots,|E(T^{(r)})|}\prod_{i=1}^r F(T_v^{(i)})$$
By induction hypothesis,
\begin{align*}
F(T_v^{(i)}) &= \frac{|T^{(i)}|!}{\prod_{w\in T^{(i)}}|T_v^{(i)}(w)|} = \frac{|T^{(i)}|!}{|T^{(i)}_v(v)|\prod_{w\neq v, w\in T^{(i)}}|T_v(w)|} \\
&=\frac{|E(T^{(i)})|!}{\prod_{w\neq v, w\in T^{(i)}}|T_v(w)|}.
\end{align*}
Therefore,
\begin{align*}
F(T_v) &= \frac{|E(T)|!}{|E(T^{(1)})|!\cdots |E(T^{(r)})|!}\prod_{i=1}^r\frac{|E(T^{(i)})|!}{\prod_{w\neq v, w\in T^{(i)}}|T_v(w)|} \\
&= \frac{|E(T)|!}{\prod_{w\neq v, w\in T} |T_v(w)|} \\
&= \frac{n!}{\prod_{w\in T} |T_v(w)|}.
\end{align*}
and the induction is complete.
\end{proof}

\begin{corollary}\label{cor:rootedTreeRatio}
Suppose that $(u,v)$ is an edge of $T$, then
$$\frac{F(T_v)}{F(T_u)} = \frac{|T_u(v)|}{|T_v(u)|} = \frac{|T_u(v)|}{n-|T_u(v)|}.$$
\end{corollary}
\begin{proof}
For any vertex $w\neq u,v$, $T_u(w)$ and $T_v(w)$ are the same subtree of $T_v$. Therefore, by Proposition~\ref{prop:rootedTreeCounting},
\begin{align*}
\frac{F(T_v)}{F(T_u)} &= \frac{\prod_{w\in T} |T_u(w)|}{\prod_{w\in T} |T_v(w)|} = \frac{|T_u(v)|\cdot |T_u(u)|}{|T_v(u)|\cdot |T_v(v)|}  \\
&= \frac{|T_u(v)|}{|T_v(u)|}  = \frac{|T_u(v)|}{n-|T_u(v)|}.
\end{align*}
\end{proof}

Corollary ~\ref{cor:rootedTreeRatio} establishes a simple relationship between the number of shellings of $T$ rooted at adjacent edges. In this way, by only calculating $F(T_v)$ for a single vertex $v$, one can quickly derive $F(T_u)$ for all $u\in T.$ For example, suppose $T$ is a path of length $n-1$, as shown in figure~\ref{fig:path}. Then $F(T_{v_1}) = 1$, and $$F(T_{v_{i+1}}) = \frac{|T_{v_i}(v_{i+1})|}{n-|T_{v_i}(v_{i+1})|}F(T_{v_i}) = \frac{n-i}{i}F(T_{v_i})$$ by corollary~\ref{cor:rootedTreeRatio}. This gives $F(T_{v_i}) = \binom{n-1}{i-1}$ for all $i=1,2,\ldots,n.$

\begin{figure}[h]
\begin{tikzpicture}[scale=1]
\draw(0,0)--(4,0);
\draw(5,0)--(7,0);

\node at (0,0){$\bullet$};
\node at (1,0){$\bullet$};
\node at (2,0){$\bullet$};
\node at (3,0){$\bullet$};

\node at (7,0){$\bullet$};
\node at (6,0){$\bullet$};

\node[draw=none] (ellipsis2) at (4.5,0) {$\cdots$};

\draw (0,0) node[below]{$v_1$};
\draw (1,0) node[below]{$v_2$};
\draw (2,0) node[below]{$v_3$};
\draw (3,0) node[below]{$v_4$};
\draw (6,0) node[below]{$v_{n-1}$};
\draw (7,0) node[below]{$v_n$};
\end{tikzpicture}
\caption{A path of length $n-1$. The shelling number is $2^{n-2}$.}
\label{fig:path}
\end{figure}

Finally, the following proposition relates the number of shellings of $T$ with that of its rooted trees.

\begin{proposition}\label{prop:treeCounting}
$$F(T) = \frac{1}{2}\sum_{v\in T} F(T_v).$$
\end{proposition}
\begin{proof}
Note that any shelling of $T$ beginning with edge $(u,v)$ is counted as a shelling of both $T_u$ and $T_v$. Thus, Proposition~\ref{prop:treeCounting} follows.
\end{proof}

\begin{example}\label{ex:path}
By Proposition~\ref{prop:treeCounting} and the discussion under Corollary~\ref{cor:rootedTreeRatio}, the number of shellings of a path of length $n-1$ is
$$\frac{1}{2}\sum_{i=1}^n \binom{n-1}{i-1} = 2^{n-2}.$$
\end{example}


\subsection{Bounds on Tree Shelling Number}
\

The goal of this section is to give several bounds of tree shelling numbers based on various parameters of a graph, such as vertex degree and diameter. A trivial upper bound is $(n-1)!$, since every shelling is also a permutation of edges. The upper bound is achieved when $T$ is a star, in which every two edges are adjacent to each other.

Here are the main theorems of the section.

\begin{theorem}\label{thm:lowerBoundDegree}
\begin{equation*}
F(T) \geq \prod_{v\in T} d(v)!,
\end{equation*}
where $d(v)$ is the degree of a vertex $v$ in $T$. The equality holds if and only if $T$ is a path of length $n-1$ or a star.
\end{theorem}
\begin{remark}
A weaker lower bound $F(T)\geq\prod_{v\in T}\big(d(v)-1\big)!$ can be shown easily by observation. However, an extra factor of $\prod_{v\in T}d(v)$ in Theorem~\ref{thm:lowerBoundDegree} requires much more efforts.
\end{remark}

\begin{theorem}\label{thm:upperBoundDiameter}
Suppose the diameter of $T$ is $\ell$. When $\ell$ is even,
$$F(T)\leq \frac{2(n-1-\frac{\ell}{2})!}{(\frac{\ell}{2})!}\bigg[\binom{n-2}{\frac{\ell}{2}}+\sum_{i=0}^{\frac{\ell}{2}-1}\binom{n-1}{i}\bigg].$$
When $\ell$ is odd,
$$F(T) \leq \frac{(n-\frac{\ell+3}{2})!}{(\frac{\ell+1}{2})!}\bigg[(n-1-\ell)\binom{n-2}{\frac{\ell-1}{2}}+n\sum_{i=0}^{\frac{\ell-1}{2}}\binom{n-1}{i}\bigg].$$
The equality holds if and only if $T$ has the following form: there exists a path $$v_0 - v_1 - \cdots -v_\ell$$ such that every edge not in this path is adjacent to $v_{\lfloor \frac{\ell}{2}\rfloor}.$
\end{theorem}

Before proving Theorem~\ref{thm:lowerBoundDegree}, it is worth noticing the following inequality, which relates the number of shellings of $T$ and $T_v$.

\begin{lemma}\label{lem:weightInequality}
Let $v$ be a vertex in $T$ and $\ell$ be the length of the longest descending path in $T_v$. Then
$$F(T)\leq \bigg[\sum_{k=0}^{\ell-1}\binom{n-2}{k}\bigg] F(T_v).$$
In particular, $F(T)\leq 2^{n-2}F(T_v).$
\end{lemma}
\begin{proof}
Let $L = v - v_1 - v_2 -\cdots - v_\ell$ be the longest descending path in $T_v$. Consider the following operations on $T$:

\begin{enumerate}
\item[1.] Suppose $i\leq \ell-2$ is the first index such that $v_i$ has a children $v'\neq v_{i+1}$ in $T_v$. Remove $T_v(v')$ and attach it on $v_{i+1}$ (i.e., children of $v'$ become children of $v_{i+1}$). Furthermore, remove edge $(v',v_i)$ and add a new edge $(v',v_{i+1}).$ This operation is illustrated in Figure~\ref{fig:pathAdjustmentForWeight}.
\item[2.] Repeat step 1 until no further operations can be performed.
\end{enumerate} 

\begin{figure}[h]
\begin{tikzpicture}[scale=1]
\draw(0,0)--(2,0);
\draw(3,0)--(6,0);
\draw(7,0)--(8,0);
\draw(4,0)--(4.5,0.866);
\draw(4,0)--(4.707,-0.707);
\draw(4,0)--(4.259,-0.966);

\node at (0,0){$\bullet$};
\node at (1,0){$\bullet$};
\node at (4,0){$\bullet$};
\node at (5,0){$\bullet$};
\node at (4.5,0.866){$\bullet$};
\node at (4.707,-0.707){$\bullet$};
\node at (4.259,-0.966){$\bullet$};
\node at (8,0){$\bullet$};

\draw[rotate around={-15:(4.5,-0.866)}] (5.5,-0.866) ellipse (1.5 and 0.5);
\draw[rotate around={15:(4.5,0.866)}] (5.5,0.866) ellipse (1.5 and 0.5);

\node[draw=none] (ellipsis2) at (2.5,0) {$\cdots$};
\node[draw=none] (ellipsis2) at (6.5,0) {$\cdots$};

\draw (0,0) node[below]{$v$};
\draw (1,0) node[below]{$v_1$};
\draw (4,0) node[below left]{$v_i$};
\draw (5,0) node[below]{$v_{i+1}$};
\draw (4.5,0.866) node[above]{$v'$};
\draw (5.5,1.1) node[]{$T_{v}(v')$};
\draw (8,0) node[below]{$v_\ell$};
\end{tikzpicture}

$$\Big\Downarrow$$

\begin{tikzpicture}[scale=1]
\draw(0,0)--(2,0);
\draw(3,0)--(6,0);
\draw(7,0)--(8,0);
\draw(5,0)--(4.5,0.866);
\draw(4,0)--(4.707,-0.707);
\draw(4,0)--(4.259,-0.966);

\node at (0,0){$\bullet$};
\node at (1,0){$\bullet$};
\node at (4,0){$\bullet$};
\node at (5,0){$\bullet$};
\node at (4.5,0.866){$\bullet$};
\node at (4.707,-0.707){$\bullet$};
\node at (4.259,-0.966){$\bullet$};
\node at (8,0){$\bullet$};

\draw[rotate around={-15:(4.5,-0.866)}] (5.5,-0.866) ellipse (1.5 and 0.5);
\draw[rotate around={36:(5,0)}] (6,0) ellipse (1.5 and 0.5);

\node[draw=none] (ellipsis2) at (2.5,0) {$\cdots$};
\node[draw=none] (ellipsis2) at (6.5,0) {$\cdots$};

\draw (0,0) node[below]{$v$};
\draw (1,0) node[below]{$v_1$};
\draw (4,0) node[below left]{$v_i$};
\draw (5,0) node[below]{$v_{i+1}$};
\draw (4.5,0.866) node[above]{$v'$};
\draw (5.8,0.6) node[]{$T_{v}(v')$};
\draw (8,0) node[below]{$v_\ell$};
\end{tikzpicture}
\caption{Operation on $T$: moving edges away from root.}
\label{fig:pathAdjustmentForWeight}
\end{figure}

Such operations preserve the length of the longest descending path in $T_v$ and would eventually stop within finite steps. Let $T^{(k)}$ be the tree after $k$th operation. For $u\in T$, define the weight of $u$ in $T^{(k)}$
$$W_k(u) = \frac{F(T^{(k)}_u)}{F(T^{(k)}_v)}.$$
We claim that the sum of weights of all vertices is non-decreasing after each operation, i.e.
\begin{equation}\label{eq:weightInequality}
\sum_{u\in T}W_k(u) \leq \sum_{u\in T}W_{k+1}(u).
\end{equation}
It suffices to prove the claim for $k=0.$
By Corollary~\ref{cor:rootedTreeRatio}, suppose $(u,w)$ is an edge in $T^{(k)}$, then
\begin{equation}\label{eq:weightRatio}
\frac{W_k(u)}{W_k(w)} = \frac{|T^{(k)}_w(u)|}{|T^{(k)}_u(w)|} = \frac{|T^{(k)}_w(u)|}{n-|T^{(k)}_w(u)|}.
\end{equation}
Therefore, suppose $v-u_1-u_2-\cdots - u_r = u$ is a path in $T^{(k)}_v$, then
\begin{equation*}
W_k(u) = \prod_{j=1}^r \frac{|T^{(k)}_v(u_j)|}{n-|T^{(k)}_v(u_j)|}.
\end{equation*}
Note that for all $u\neq v', v_{i+1}$, $|T^{(1)}_v(u)| = |T_v(u)|$. For $w\not\in T_v(v')\cup T_v(v_{i+1})$, $v',v_{i+1}$ are not on the path from $v$ to $w$, so
\begin{equation*}
W_0(w) = W_1(w).
\end{equation*}
Write $|T_v(v'))|=a, |T_v(v_{i+1})| = b$, then $|T^{(1)}_v(v')| = 1$, $|T^{(1)}_v(v_{i+1})| = |T_v(v')|+|T_v(v_{i+1})| = a+b.$ By (\ref{eq:weightRatio}),
$$W_0(v') = \frac{a}{n-a}W_0(v_i).$$
$$W_0(v_{i+1}) = \frac{b}{n-b}W_0(v_i).$$
$$W_1(v_{i+1}) = \frac{a+b}{n-a-b}W_1(v_i).$$
Since $W_0(v_i) = W_1(v_i)$,
\begin{equation*}
W_0(v')+W_0(v_{i+1})\leq W_1(v_{i+1}).
\end{equation*}
For $w\in T_v(v')\setminus\{v'\}$, by (\ref{eq:weightRatio}), 
\begin{equation*}
\frac{W_1(w)}{W_1(v_{i+1})} = \frac{W_0(w)}{W_0(v')} \implies W_0(w)\leq W_1(w).
\end{equation*}
Similarly, for $w\in T_v(v_{i+1})\setminus\{v_{i+1}\}$,
\begin{equation*}
\frac{W_1(w)}{W_1(v_{i+1})} = \frac{W_0(w)}{W_0(v_{i+1})}\implies W_0(w)\leq W_1(w).
\end{equation*}
Therefore, we conclude that
$$\sum_{w\in T} W_0 (w)\leq \sum_{w\in T} W_1(w),$$
and (\ref{eq:weightInequality}) is proved.

Finally, suppose the operation stops after step $M$, then $T^{(M)}$ is the tree where all vertices not in $L$ are incident to $v_{\ell-1}$. Thus, by~\ref{eq:weightRatio},
\begin{align*}
\sum_{u\in T} W_{M}(u) &= W_M(v)+W_M(v_1)+\cdots+W_M(v_{\ell-1}) + (n-\ell)W_M(v_\ell) \\
&=\sum_{i=0}^{\ell-1}\binom{n-1}{i} + (n-l)\frac{\binom{n-1}{\ell-1}}{n-1}\\
&=2\sum_{i=0}^{\ell-1}\binom{n-2}{i}.
\end{align*}
According to equation (\ref{eq:weightInequality}), Proposition~\ref{prop:treeCounting}, 
$$\frac{F(T)}{F(T_v)} = \frac{1}{2}\sum_{u\in T}W_0(u) \leq \frac{1}{2}\sum_{u\in T}W_M(u) = \sum_{i=0}^{\ell-1}\binom{n-2}{i},$$
so the proof is complete.
\end{proof}

Now we are ready to prove Theorem~\ref{thm:lowerBoundDegree} and ~\ref{thm:upperBoundDiameter}.
\begin{proof}[Proof of Theorem~\ref{thm:lowerBoundDegree}]
Induct on $|T|$. When $|T| = 2$, $F(T) = 2 = \prod_{v\in T} d(v)!$. The equality holds if and only if $T$ is a path (in this case $T$ is also a star).

Assume that statement holds for all $|T|<n$, consider the case where $|T| = n$. If $|T|$ is a path of length $n-1$, then by Example~\ref{ex:path},
$$F(T) = 2^{n-2} = \prod_{v\in T} d(v)!,$$
as desired. 

Suppose that $T$ is not a single path, then there exists a vertex $v$ of degree $d\geq 3.$ Let $u_1,u_2,\ldots,u_d$ be vertices adjacent to $v$ and write $|T_v(u_i)| = s_i$ for $i=1,2,\ldots,d$. Assume $s_1\leq s_2\leq \ldots \leq s_d.$ Let $T'$ be the subtree of $T$ obtained by removing all vertices in $T_v(u_1)$ and all edges incident to those vertices. Let $T''$ be the subtree of $T$ induced by edges in $E(T)\setminus E(T').$ See Figure~\ref{fig:theoremLowerBound} for illustration.

\begin{figure}[h]
\begin{tikzpicture}[scale=1]
\draw(0,0)--(1,0);
\draw(0,0)--(0,1);
\draw(0,0)--(0,-1);
\draw(0,0)--(-0.866,-0.5);
\draw(0,0)--(-0.866,0.5);

\node at (0,0){$\bullet$};
\node at (1,0){$\bullet$};
\node at (0,1){$\bullet$};
\node at (0,-1){$\bullet$};
\node at (-0.866,-0.5){$\bullet$};
\node at (-0.866,0.5){$\bullet$};

\draw (1.5,0) ellipse (2 and 0.5);
\draw (-0.7,0) ellipse (1.3 and 2);

\draw (0,0) node[below right]{$v$};
\draw (1,0) node[below]{$u_1$};
\draw (0,1) node[above]{$u_2$};
\draw (-0.866,0.5) node[above]{$u_3$};
\draw (0,-1) node[below]{$u_d$};
\draw (2,0) node[]{$T''$};
\draw (-1.2,0) node[]{$T'$};
\end{tikzpicture}
\caption{Merging a shelling of $T'$ and $T''_v$ to a shelling of $T$.}
\label{fig:theoremLowerBound}
\end{figure}

Suppose $\sigma'$ is a shelling of $T'$ and $\sigma''$ a shelling of $T''_v$. Consider the following method to merge $\sigma'$ and $\sigma''$ into $\sigma$, a permutation of $E(T)$, such that (i) the order of edges in $\sigma'$ and in $\sigma''$ are preserved; (ii) $\sigma''(1) = (v,u_1)$ is not one of the first $s_d$ edges after merge. Note that $\sigma$ must be a shelling of $T$, since at least one of $\{\sigma'(k): 1\leq k\leq s_d\}$ is incident to $v$ and $(v,u_1)$ is adjacent to some previous edges in $\sigma$.

For fixed $\sigma'$ and $\sigma''$, the number of $\sigma$ constructed by the above merging method is 
$$\binom{n-1-s_d}{|E(T'')|} = \binom{s_1+s_2+\cdots s_{d-1}}{s_1}.$$
Therefore,
\begin{equation}\label{eq:shellingExtensionNumber}
F(T) \geq F(T')F(T''_v)\binom{s_1+s_2+\cdots+ s_{d-1}}{s_1}.
\end{equation}
Note that the shellings of $T$ constructed above do not include those whose first edge is $(v,u_1)$, so we can replace ``$\geq$" with ``$>$" in (\ref{eq:shellingExtensionNumber}).
Furthermore, by Lemma~\ref{lem:weightInequality},
$$F(T''_v) \geq \frac{F(T'')}{2^{s_1-1}}.$$
By induction hypothesis,
$$F(T')F(T'') \geq \frac{1}{d}\prod_{u\in T} d(u)!.$$
Thus, (\ref{eq:shellingExtensionNumber}) implies
$$F(T) > \frac{1}{2^{s_1-1}d}\binom{s_1+s_2+\cdots+s_{d-1}}{s_1}\prod_{u\in T}d(u)!.$$


If for some choices of $v$ with degree $d\geq 3$, $\binom{s_1+s_2+\cdots+s_{d-1}}{s_1} \geq 2^{s_1-1}d$, then $F(T) > \prod_{u\in T} d(u)!$ and equality never holds.

If not, for all choices of $v$, $\binom{s_1+s_2+\cdots+s_{d-1}}{s_1} < 2^{s_1-1}d.$ 
By Lemma~\ref{app:ineq1}, $s_1 = s_2 =  \cdots = s_{d-1} = 1.$
Therefore, $T$ must be the following type of trees: for every vertex $v$ of degree $d(v) \geq 3$, it connects at least $d(v) - 1$ leaves. If $T$ is a star, then $F(T) = (n-1)!$ is an equality case. If not, $T$ has the form shown in Figure~\ref{fig:Stars}, where $v_0$ and $v_m$ are the only two possible vertices with degree at least 3. 

\begin{figure}[h]
\begin{tikzpicture}[scale=1]
\draw(0,0)--(2,0);
\draw(3,0)--(4,0);
\draw(0,0)--(0,1);
\draw(0,0)--(0,-1);
\draw(0,0)--(-0.707,0.707);
\draw(0,0)--(-1,0);
\draw(4,0)--(4,-1);
\draw(4,0)--(4,1);
\draw(4,0)--(5,0);
\draw(4,0)--(4.707,0.707);

\node[draw=none] (ellipsis2) at (2.5,0) {$\cdots$};
\node at (0,0){$\bullet$};
\node at (1,0){$\bullet$};
\node at (0,1){$\bullet$};
\node at (0,-1){$\bullet$};
\node at (-0.707,0.707){$\bullet$};
\node at (-1,0){$\bullet$};
\node at (4,0){$\bullet$};
\node at (5,0){$\bullet$};
\node at (4,1){$\bullet$};
\node at (4,-1){$\bullet$};
\node at (4.707,0.707){$\bullet$};
\node[rotate around={45:(0,0)}] (ellipsis1) at (-0.55,-0.45) {$\vdots$};
\node[rotate around={45:(0,0)}] (ellipsis1) at (4.5,-0.5) {$\cdots$};

\draw (0,0) node[below right]{$v_0$};
\draw (1,0) node[below]{$v_1$};
\draw (4,0) node[below left]{$v_m$};
\end{tikzpicture}
\caption{The only type of trees that satisfy case 2 condition.}
\label{fig:Stars}
\end{figure} 

Suppose $d(v_0) = d_1$, $d(v_m) = d_2$ with $2\leq d_1\leq d_2$. If $m=1$, by Proposition~\ref{prop:rootedTreeCounting}, ~\ref{prop:treeCounting}, and Lemma~\ref{app:ineq2},
\begin{align*}
F(T) &= \frac{d_1^2+d_2^2+d_1d_2-d_1-d_2}{d_1d_2}(d_1+d_2-2)! \\
&\geq 2\cdot(d_1+d_2-2)!\\
&\geq d_1!d_2! = \prod_{u\in T} d(u)!.
\end{align*}
The equality holds only if $d_1 = d_2 = 2$ and $T$ is a single path.

Now suppose $m\geq 2.$ Consider the following type of shelling of $T$: The first $m-1$ edges of $\sigma$ consist of $\{(v_i,v_{i+1}): 0\leq i\leq m-2\}$. The number of shellings of such type is
$$2^{m-2}(d_1-1)!(d_2-1)!\binom{d_1+d_2-1}{d_2}.$$
Similarly, the number of shellings whose first $m-1$ edges consist of $\{(v_i,v_{i+1}): 1\leq i\leq m-1\}$ is
$$2^{m-2}(d_1-1)!(d_2-1)!\binom{d_1+d_2-1}{d_1}.$$
Thus by Lemma~\ref{app:ineq3},
\begin{align*}
F(T) &\geq 2^{m-2}(d_1-1)!(d_2-1)!\bigg[\binom{d_1+d_2-1}{d_2}+\binom{d_1+d_2-1}{d_1}\bigg] \\
&= 2^{m-2}(d_1-1)!(d_2-1)!\binom{d_1+d_2}{d_1}\\
&> 2^{m-1}d_1!d_2! = \prod_{u\in T}d(u)!
\end{align*}
unless $d_1=2, d_2\leq 4$, in which cases we have:
\begin{itemize}
\item $(d_1,d_2) = (2,2).$ $F(T) = 2^{n-2} = \prod_{u\in T}d(u)!.$ In this equality case, $T$ is a single path.
\item $(d_1,d_2) = (2,3).$ $F(T) = 2^{n-1}-2 > 3!\cdot 2^{n-4} = \prod_{u\in T}d(u)!.$
\item $(d_1,d_2) = (2,4).$ $F(T) = 6(2^{n-2}-n+1) > 4!\cdot 2^{n-5} = \prod_{u\in T}d(u)!.$
\end{itemize}

By induction, the proof of Theorem~\ref{thm:lowerBoundDegree} is complete.
\end{proof}


\begin{proof}[Proof of Theorem~\ref{thm:upperBoundDiameter}]
Let $v_0 - v_1 -\cdots - v_\ell$ be a longest path in $T$. Firstly, we reduce the problem to the case where all edges in $T$ are incident to $\{v_1,v_2,\ldots,v_{\ell-1}\}$. If not, construct a new tree $T'$ by removing every edge $e$ not incident to $\{v_i:1\leq i\leq \ell-1\}$ and adding a corresponding edge incident to $v_j$, where $v_j$ is the closest vertex from $e$ among $L$. Every shelling of $T$ is still a shelling of $T'$ by considering the corresponding edges. Thus, $F(T)\leq F(T')$ while the longest path remains the same.

Under this assumption, denote $V' = T\setminus \{v_0,v_1,\ldots,v_\ell\}.$ Consider the following operations:
\begin{enumerate}
\item[1.] Let $i$ be the smallest index such that $v_i$ has degree $\geq 3.$ If $i<\frac{\ell}{2}$, we remove all edges of the form $(v_i,u)$ for $u\in V'$ and add edges $(u,v_{i+1}).$
\item[2.] Repeat step 1 until no further operations can be performed.
\item[3.] Let $j$ be the largest index such that $v_j$ has degree $\geq 3.$ If $j>\frac{\ell}{2}$, we remove all edges of the form $(v_j,u)$ for $u\in V'$ and add edges $(u,v_{j-1}).$
\item[4.] Repeat step 3 until no further operations can be performed.
\end{enumerate}

\begin{figure}[h]
\begin{tikzpicture}[scale=1.3]
\draw(1,0)--(7,0);
\draw(2.293,0.707)--(3,0)--(3.707,0.707);
\draw(3,0)--(3,1);
\draw(4,-1)--(4,0);
\draw(4.5,-0.866)--(5,0)--(5.5,-0.866);
\draw(6,0)--(6,1);
\node at (1,0){$\bullet$};
\node at (2,0){$\bullet$};
\node at (3,0){$\bullet$};
\node at (4,0){$\bullet$};
\node at (5,0){$\bullet$};
\node at (6,0){$\bullet$};
\node at (7,0){$\bullet$};
\node at (2.293,0.707){$\bullet$};
\node at (3,1){$\bullet$};
\node at (3.707,0.707){$\bullet$};
\node at (4,-1){$\bullet$};
\node at (4.5,-0.866){$\bullet$};
\node at (5.5,-0.866){$\bullet$};
\node at (6,1){$\bullet$};
\draw (1.5,0) node[below]{5};
\draw (2.5,0) node[below]{2};
\draw (3.5,0) node[below]{4};
\draw (4.5,0) node[below]{6};
\draw (5.5,0) node[below]{10};
\draw (6.5,0) node[below]{11};
\draw (2.5,0.5) node[below]{1};
\draw (2.95,0.55) node[right]{8};
\draw (3.5,0.5) node[below]{3};
\draw (4,-0.5) node[left]{9};
\draw (4.7,-0.5) node[left]{7};
\draw (5.3,-0.5) node[right]{13};
\draw (6,0.5) node[right]{12};
\end{tikzpicture}

$$\Big\Downarrow$$

\begin{tikzpicture}[scale=1.3]
\draw(1,0)--(7,0);
\draw(3.293,0.707)--(4,0)--(4.707,0.707);
\draw(4,0)--(4,1);
\draw(4,-1)--(4,0);
\draw(4.5,-0.866)--(5,0)--(5.5,-0.866);
\draw(6,0)--(6,1);
\node at (1,0){$\bullet$};
\node at (2,0){$\bullet$};
\node at (3,0){$\bullet$};
\node at (4,0){$\bullet$};
\node at (5,0){$\bullet$};
\node at (6,0){$\bullet$};
\node at (7,0){$\bullet$};
\node at (3.293,0.707){$\bullet$};
\node at (4,1){$\bullet$};
\node at (4.707,0.707){$\bullet$};
\node at (4,-1){$\bullet$};
\node at (4.5,-0.866){$\bullet$};
\node at (5.5,-0.866){$\bullet$};
\node at (6,1){$\bullet$};
\draw (1.5,0) node[below]{10};
\draw (2.5,0) node[below]{6};
\draw (3.5,0) node[below]{4};
\draw (4.5,0) node[below]{2};
\draw (5.5,0) node[below]{5};
\draw (6.5,0) node[below]{11};
\draw (3.5,0.5) node[below]{1};
\draw (3.95,0.55) node[right]{8};
\draw (4.5,0.5) node[below]{3};
\draw (4,-0.5) node[left]{9};
\draw (4.7,-0.5) node[left]{7};
\draw (5.3,-0.5) node[right]{13};
\draw (6,0.5) node[right]{12};

\end{tikzpicture}
\caption{An example of operation on $T$: moving edges towards middle. The shellings are indicated by the number on the edges. $g$ maps a shelling of the first tree to a shelling of the second tree.}
\label{fig:theoremUpperBound}
\end{figure}

Suppose the above operations end in step $M$. Let $T^{(t)}$ be the tree after $t^{\text{th}}$ operation. We claim that for all $t<M$,
\begin{equation*}
F(T^{(t+1)}) \geq F(T^{(t)}).
\end{equation*}
It suffices to prove the case when $t = 0.$ By symmetry, we can assume $i<\frac{\ell}{2}$. Let $V_i$ be the set of vertices adjacent to $v_i$ in $T$ except $v_{i-1}, v_{i+1}$. 
Define 
\begin{align*}
S_{T\cap T^{(1)}} &:= \{\sigma\text{ is a shelling of }T: \exists u\in V_i, (v_i,u) \text{ appears after }(v_i,v_{i+1}) \text{ in } \sigma\}, \\
S_{T^{(1)}\cap T} &:= \{\tau\text{ is a shelling of }T^{(1)}: \exists u\in V_i, (v_{i+1},u) \text{ appears after }(v_i,v_{i+1}) \text{ in } \tau\}, \\
S_{T\setminus T^{(1)}} &:= \{\sigma\text{ is a shelling of }T: \exists u\in V_i, (v_i,u) \text{ appears before }(v_i,v_{i+1}) \text{ in } \sigma\},\\
S_{T^{(1)}\setminus T} &:= \{\tau\text{ is a shelling of }T^{(1)}: \exists u\in V_i, (v_{i+1},u) \text{ appears before }(v_i,v_{i+1}) \text{ in } \tau\}.
\end{align*}

Note that there is a bijection between $S_{T\cap T^{(1)}}$ and $S_{T^{(1)}\cap T}$ by replacing edges of the form $(v_i,u)$ in every $\sigma\in S_{T\cap T^{(1)}}$ with $(v_{i+1},u)$, for all $u\in V_i$. Thus, $|S_{T\cap T^{(1)}}|=|S_{T^{(1)}\cap T}|$ and
$$F(T^{(1)}) - F(T) = |S_{T^{(1)}\setminus T}| - |S_{T\setminus T^{(1)}}|.$$
Consider a function $g: S_{T\setminus T^{(1)}} \rightarrow S_{T^{(1)}\setminus T}$. For $\sigma \in S_{T\setminus T^{(1)}}$, define $\tau = g(\sigma)$ as follows. If $\sigma(k) = (v_i, u)$ for some $u\in V_i$, $\tau(k) = (v_{i+1}, u)$; if $\sigma(k) = (v_j,u)$ for some $j\neq i$ and $u\in V'$, $\tau(k) = (v_j,u)$. It remains to define $\tau(k)$'s where $\sigma(k)$ is an edge of $L$.

Write $e(j) = (v_{j},v_{j+1})$ for $j=0,1,\ldots,\ell-1.$ For $1\leq r\leq \ell$, suppose $\sigma(k_r) = e(j_r)$ where $k_1<k_2<\cdots < k_\ell.$ Define $\tau(k_r)$ inductively: when $r=1$, $\tau(k_1) = e(2i-j_1).$ When $r\geq 2$,
$$\tau(k_{r}) = \begin{cases}
e(j_{r}), & \text{ if } \{\tau(k_1), \tau(k_2),\ldots, \tau(k_{r-1})\} =\{e(j_1), e(j_2),\ldots, e(j_{r-1})\}  \\
e(2i-j_{r}), & \text{ otherwise.}
\end{cases}$$
The idea is that $g$ maps edges not in $L$ to the corresponding edges. For edges in $L$, $g$
acts as a reflection with respect to $e(i)$, until the reflection image matches with the preimage. An example of $g$ is in Figure~\ref{fig:theoremUpperBound}.

We check the following properties of $g$:
\begin{itemize}
\item $g$ is well-defined. 

We first note that for any $r\leq \ell$, both $\{\sigma(k_1),\sigma(k_2),\ldots,\sigma(k_r)\}$ and $\{\tau(k_1),\tau(k_2),\ldots,\tau(k_r)\}$ form a path $P_r$ and $P^{(1)}_r$ in $L$, respectively. Since $j_1 \leq i$, the right endpoint of $P^{(1)}_r$ is never on the left side of the right endpoint of $P_r$ (assuming that $L$ is a horizontal path with left endpoint $v_0$ and right endpoint $v_\ell$, as illustrated in Figure~\ref{fig:theoremUpperBound}). Furthermore, since the ``branching edges" of $T$ (edges in $E(T)\setminus E(L)$) are not on the left side of $v_i$, every branching edge adjacent to $P_r$ must be adjacent to $P^{(1)}_r$. Thus, $\tau$ is a shelling of $T^{(1)}$. Moreover, $\tau\in S_{T^{(1)}\setminus T}$ by the correspondence between $(v_i,u)\in \sigma$ and $(v_{i+1},u)\in \tau$ for all $u\in V_i$. Therefore, $g$ is well-defined.

\item $g$ is injective.

Suppose $g(\sigma) = \tau.$ By the definition of $g$, $\sigma(k)$ is uniquely determined whenever $\tau(k) \not\in L.$ Suppose $\tau(k_r) = e(i_r)$ for $1\leq r\leq \ell$. we can recover $\sigma(k_r)$ from $\tau$: $\sigma(k_1) = e(2i-i_1)$. When $r\geq 2$,
$$\sigma(k_{r}) = \begin{cases}
e(i_{r}), & \text{ if } \{\sigma(k_1), \sigma(k_2),\ldots, \sigma(k_{r-1})\} =\{e(i_1), e(i_2),\ldots, e(i_{r-1})\}  \\
e(2i-i_{r}), & \text{ otherwise.}
\end{cases}$$
Therefore, $\sigma$ is uniquely determined by $\tau$ and $g$ is injective.
\end{itemize}

Since $g$ is injective, $|S_{T^{(1)}\setminus T}| \geq |S_{T\setminus T^{(1)}}|$ and thus $F(T^{(1)}) \geq F(T).$

Finally, note that $T^{(M)}$ is the tree where all edges not in $L$ are incident to $v_{\lfloor\frac{\ell}{2}\rfloor}$. By Proposition~\ref{prop:rootedTreeCounting} and ~\ref{prop:treeCounting},
$$F(T^{(M)})= 
\begin{cases}
\frac{2(n-1-\frac{\ell}{2})!}{(\frac{\ell}{2})!}\bigg[\binom{n-2}{\frac{\ell}{2}}+\sum_{i=0}^{\frac{\ell}{2}-1}\binom{n-1}{i}\bigg], &\text{ if }\ell \text{ is even,} \\
\frac{(n-\frac{\ell+3}{2})!}{(\frac{\ell+1}{2})!}\bigg[(n-1-\ell)\binom{n-2}{\frac{\ell-1}{2}}+n\sum_{i=0}^{\frac{\ell-1}{2}}\binom{n-1}{i}\bigg], &\text{ if } \ell \text{ is odd.}
\end{cases}
$$
Thus, the proof of inequality is complete.

Futhermore, we shall prove that $g$ is surjective only if $T$ is isomorphic to $T^{(M)}.$ If not, then there are two cases:

\noindent \textbf{Case 1.} $i< \frac{\ell-1}{2}$.

In this case, $2i<\ell-1$. Thus, for every $\sigma \in S_{T\setminus T^{(1)}}$, $g(\sigma)(1)\neq e(\ell-1) = (v_{\ell-1},v_\ell)$. However, there exists $\tau\in S_{T^{(1)}\setminus T}$ whose first edge is $(v_{\ell-1},v_{\ell})$, contradiction!

\noindent \textbf{Case 2.} $i= \frac{\ell-1}{2}$ and there exists another vertex $v_j$ of degree at least 3.

Suppose $(v_j, u)$ is an edge not in $L$, then for every $\sigma \in S_{T\setminus T^{(1)}}$, $g(\sigma)(1)$ cannot be this edge. However, there exists $\tau\in S_{T^{(1)}\setminus T}$ whose first edge is $(v_j,u)$, contradiction!

Therefore, $g$ is surjective only if $T$ is isomorphic to $T^{(M)}$, so $$F(T) = F(T^{(M)})$$ if and only if $T$ is isormorphic to $T^{(M)}$. This completes the proof of Theorem~\ref{thm:upperBoundDiameter}.
\end{proof}


\section*{Acknowledgements}
This research was carried out as part of the 2018 Summer Program in Undergraduate Research (SPUR) of the MIT Mathematics Department. The authors would like to thank Prof. Richard Stanley for suggesting the project and Prof. Ankur Moitra and Prof. Davesh Maulik for helpful suggestions.

\bibliographystyle{plain}

2018-09-28T02:04:40.000
1809
1809.10263
en
https://arxiv.org/abs/1809.10263
A shelling of a graph, viewed as an abstract simplicial complex that is pure of dimension 1, is an ordering of its edges such that every edge is adjacent to some other edges appeared previously. In this paper, we focus on complete bipartite graphs and trees. For complete bipartite graphs, we obtain an exact formula for their shelling numbers. And for trees, we relate their shelling numbers to linear extensions of tree posets and bound shelling numbers using vertex degrees and diameter.
Combinatorics (math.CO)
Counting Shellings of Complete Bipartite Graphs and Trees
Qwen/Qwen-72B
1. YES
2. YES