Here are two proofs of your identity, which I have hinted at in my comments.
The identity
Let me first restate your identity with the letter $k$ renamed as $n$:
Theorem 1. Let $n\geq2$ be an integer. Then,
$$
n^{n-3}=\dfrac{1}{2}\sum\limits_{i=1}^{n-1}\dbinom{n-2}{i-1}i^{i-2}\left(
n-i\right) ^{n-i-2}.
$$
First proof: the Abel identity and its friends
The first proof of Theorem 1 will actually show a more general identity:
Theorem 2. Let $n$ be a nonnegative integer. In the polynomial ring
$\mathbb{Z}\left[ x,y,z\right] $, we have
$$
\sum\limits_{k=0}^{n}\dbinom{n}{k}xy\left( x-kz\right) ^{k-1}\left( y-\left(
n-k\right) z\right) ^{n-k-1}=\left( x+y\right) \left( x+y-nz\right)
^{n-1}.
$$
Note that both sides of the equality in Theorem 2 are well-defined polynomials
in $\mathbb{Z}\left[ x,y,z\right] $ (not just rational functions in
$\mathbb{Q}\left( x,y,z\right) $): Indeed,
the only denominators that appear on the left hand side arise from the
$\left( x-kz\right) ^{k-1}$ term for $k=0$ and from the $\left( y-\left(
n-k\right) z\right) ^{n-k-1}$ term for $k=n$; but both of them are cancelled
by the $xy$ factor appearing in each addend.
the only denominator that appears on the right hand side arises from the
$\left( x+y-nz\right) ^{n-1}$ term for $n=0$; but this denominator is
cancelled by the $x+y$ factor.
Theorem 2 is a well-known fact in umbral calculus: It says that the sequence
of the Abel polynomials (the sequence $\left( p_{0},p_{1},p_{2}
,\ldots\right) $ whose $n$-th term is $p_{n}=x\left( x-nz\right) ^{n-1}$,
where $x$ is considered an indeterminate and $z$ a constant) is of binomial
type (i.e., it satisfies $p_{n}\left( x+y\right) =\sum\limits_{k=0}^{n}\dbinom
{n}{k}p_{k}\left( x\right) p_{n-k}\left( y\right) $). As such, it is
probably proven all across the literature. I also think that Theorem 2 is what
the equation (2) in Victor J. W. Guo, Bijective proofs of Gould-Mohanty's
and Raney-Mohanty's identities,
arXiv:1005.4258v1 is supposed to be (I say
"supposed" because equation (2) as it appears in Guo's preprint is false).
Let me derive Theorem 2 from an even better known identity, namely the Abel
identity (appearing as equation (1) in the above-cited paper by Victor J. W.
Guo):
Theorem 3. Let $n$ be a nonnegative integer. In the polynomial ring
$\mathbb{Z}\left[ x,y,z\right] $, we have
$$
\sum\limits_{k=0}^{n}\dbinom{n}{k}x\left( x-kz\right) ^{k-1}\left( y+kz\right)
^{n-k}=\left( x+y\right) ^{n}.
$$
As before, both sides of the equality in Theorem 3 are well-defined
polynomials in $\mathbb{Z}\left[ x,y,z\right] $.
The most well-known particular case of Theorem 3 is probably the one obtained
by substituting $-1$ for $z$:
Theorem 4. Let $n$ be a nonnegative integer. In the polynomial ring
$\mathbb{Z}\left[ x,y\right] $, we have
$$
\sum\limits_{k=0}^{n}\dbinom{n}{k}x\left( x+k\right) ^{k-1}\left( y-k\right)
^{n-k}=\left( x+y\right) ^{n}.
$$
Theorem 4 appears in many places, e.g. (with a boring proof) in my solution
to Problem 4 on the 6th QEDMO 2009 (scroll down to Theorem 4). Yes, I am that lazy at
reference hunting. $\square$
I am going to reverse the cart and derive Theorem 1 back from Theorem 4. The
first step is getting Theorem 3:
Proof of Theorem 3. Work in the field $\mathbb{Q}\left( x,y,z\right) $ of
rational functions in $x,y,z$. Substitute $\dfrac{x}{z}$ and $\dfrac{y}{z}$
for $x$ and $y$ in Theorem 4. The result is
$$
\sum\limits_{k=0}^{n}\dbinom{n}{k}\dfrac{x}{z}\left( \dfrac{x}{z}-k\right)
^{k-1}\left( \dfrac{y}{z}+k\right) ^{n-k}=\left( \dfrac{x}{z}+\dfrac{y}
{z}\right) ^{n}.
$$
Multiplying this equality by $z^{n}$ and clearing denominators results in
$$
\sum\limits_{k=0}^{n}\dbinom{n}{k}x\left( x-kz\right) ^{k-1}\left( y+kz\right)
^{n-k}=\left( x+y\right) ^{n}.
$$
Thus, Theorem 3 is proven. $\square$
Next, I shall derive Theorem 2 from Theorem 3:
Proof of Theorem 2. Substituting $y-nz$ for $y$ in Theorem 3 yields
$$
\sum\limits_{k=0}^{n}\dbinom{n}{k}x\left( x-kz\right) ^{k-1}\left( y-nz+kz\right)
^{n-k}=\left( x+y-nz\right) ^{n}.
$$
Thus,
\begin{align}
\left( x+y-nz\right) ^{n} & =\sum\limits_{k=0}^{n}\dbinom{n}{k}x\left(
x-kz\right) ^{k-1}\left( \underbrace{y-nz+kz}_{=y-\left( n-k\right)
z}\right) ^{n-k}\nonumber\\
\tag{1}
& =\sum\limits_{k=0}^{n}\dbinom{n}{k}x\left( x-kz\right) ^{k-1}\left( y-\left(
n-k\right) z\right) ^{n-k}.
\label{pf.t2.1}
\end{align}
Multiplying this equality by $y$, we find
\begin{align}
y\left( x+y-nz\right) ^{n} & =y\sum\limits_{k=0}^{n}\dbinom{n}{k}x\left(
x-kz\right) ^{k-1}\left( y-\left( n-k\right) z\right) ^{n-k}\nonumber\\
& =\sum\limits_{k=0}^{n}\dbinom{n}{k}xy\left( x-kz\right) ^{k-1}\underbrace{\left(
y-\left( n-k\right) z\right) ^{n-k}}_{=\left( y-\left( n-k\right)
z\right) \left( y-\left( n-k\right) z\right) ^{n-k-1}}\nonumber\\
& =\sum\limits_{k=0}^{n}\dbinom{n}{k}xy\left( x-kz\right) ^{k-1}\left( y-\left(
n-k\right) z\right) \left( y-\left( n-k\right) z\right) ^{n-k-1}
\nonumber\\
\tag{2}
& =\sum\limits_{k=0}^{n}\left( y-\left( n-k\right) z\right) \dbinom{n}
{k}xy\left( x-kz\right) ^{k-1}\left( y-\left( n-k\right) z\right)
^{n-k-1}.
\label{pf.t2.2}
\end{align}
On the other hand, substituting $y$ and $x$ for $x$ and $y$ in \eqref{pf.t2.1},
we obtain
\begin{align*}
\left( y+x-nz\right) ^{n} & =\sum\limits_{k=0}^{n}\dbinom{n}{k}y\left(
y-kz\right) ^{k-1}\left( x-\left( n-k\right) z\right) ^{n-k}\\
& =\sum\limits_{k=0}^{n}\dbinom{n}{n-k}y\left( y-\left( n-k\right) z\right)
^{n-k-1}\left( x-\left( n-\left( n-k\right) \right) z\right) ^{n-\left(
n-k\right) }
\end{align*}
(here, we have substituted $n-k$ for $k$ in the sum). Since $y+x=x+y$, this
rewrites as
\begin{align*}
& \left( x+y-nz\right) ^{n}\\
& =\sum\limits_{k=0}^{n}\underbrace{\dbinom{n}{n-k}}_{=\dbinom{n}{k}}y\left(
y-\left( n-k\right) z\right) ^{n-k-1}\underbrace{\left( x-\left(
n-\left( n-k\right) \right) z\right) ^{n-\left( n-k\right) }
}_{\substack{=\left( x-kz\right) ^{k}\\=\left( x-kz\right) \left(
x-kz\right) ^{k-1}}}\\
& =\sum\limits_{k=0}^{n}\dbinom{n}{k}y\left( y-\left( n-k\right) z\right)
^{n-k-1}\left( x-kz\right) \left( x-kz\right) ^{k-1}\\
& =\sum\limits_{k=0}^{n}\dbinom{n}{k}y\left( x-kz\right) \left( x-kz\right)
^{k-1}\left( y-\left( n-k\right) z\right) ^{n-k-1}.
\end{align*}
Multiplying this equality by $x$, we obtain
\begin{align*}
x\left( x+y-nz\right) ^{n} & =x\sum\limits_{k=0}^{n}\dbinom{n}{k}y\left(
x-kz\right) \left( x-kz\right) ^{k-1}\left( y-\left( n-k\right)
z\right) ^{n-k-1}\\
& =\sum\limits_{k=0}^{n}\dbinom{n}{k}xy\left( x-kz\right) \left( x-kz\right)
^{k-1}\left( y-\left( n-k\right) z\right) ^{n-k-1}\\
& =\sum\limits_{k=0}^{n}\left( x-kz\right) \dbinom{n}{k}xy\left( x-kz\right)
^{k-1}\left( y-\left( n-k\right) z\right) ^{n-k-1}.
\end{align*}
Adding this equality to \eqref{pf.t2.2}, we find
\begin{align*}
& y\left( x+y-nz\right) ^{n}+x\left( x+y-nz\right) ^{n}\\
& =\sum\limits_{k=0}^{n}\left( y-\left( n-k\right) z\right) \dbinom{n}
{k}xy\left( x-kz\right) ^{k-1}\left( y-\left( n-k\right) z\right)
^{n-k-1}\\
& \ \ \ \ \ \ \ \ \ \ +\sum\limits_{k=0}^{n}\left( x-kz\right) \dbinom{n}
{k}xy\left( x-kz\right) ^{k-1}\left( y-\left( n-k\right) z\right)
^{n-k-1}\\
& =\sum\limits_{k=0}^{n}\underbrace{\left( \left( y-\left( n-k\right) z\right)
+\left( x-kz\right) \right) }_{=x+y-nz}\dbinom{n}{k}xy\left( x-kz\right)
^{k-1}\left( y-\left( n-k\right) z\right) ^{n-k-1}\\
& =\sum\limits_{k=0}^{n}\left( x+y-nz\right) \dbinom{n}{k}xy\left( x-kz\right)
^{k-1}\left( y-\left( n-k\right) z\right) ^{n-k-1}\\
& =\left( x+y-nz\right) \sum\limits_{k=0}^{n}\dbinom{n}{k}xy\left( x-kz\right)
^{k-1}\left( y-\left( n-k\right) z\right) ^{n-k-1}.
\end{align*}
Thus,
\begin{align*}
& \left( x+y-nz\right) \sum\limits_{k=0}^{n}\dbinom{n}{k}xy\left( x-kz\right)
^{k-1}\left( y-\left( n-k\right) z\right) ^{n-k-1}\\
& =y\left( x+y-nz\right) ^{n}+x\left( x+y-nz\right) ^{n}=\left(
y+x\right) \left( x+y-nz\right) ^{n}\\
& =\left( x+y\right) \left( x+y-nz\right) ^{n}.
\end{align*}
Dividing this equality by $x+y-nz$, we obtain
$$
\sum\limits_{k=0}^{n}\dbinom{n}{k}xy\left( x-kz\right) ^{k-1}\left( y-\left(
n-k\right) z\right) ^{n-k-1}=\left( x+y\right) \left( x+y-nz\right)
^{n-1}.
$$
This proves Theorem 2. $\square$
Finally, we can get Theorem 1:
First proof of Theorem 1. Theorem 2 (applied to $n-2$ instead of $n$) shows
that in the polynomial ring $\mathbb{Z}\left[ x,y,z\right] $, we have
\begin{align*}
& \sum\limits_{k=0}^{n-2}\dbinom{n-2}{k}xy\left( x-kz\right) ^{k-1}\left(
y-\left( \left( n-2\right) -k\right) z\right) ^{\left( n-2\right)
-k-1}\\
& =\left( x+y\right) \left( x+y-\left( n-2\right) z\right) ^{n-3}.
\end{align*}
Substituting $1$, $1$ and $-1$ for $x$, $y$ and $z$ in this equality (and
making the obvious simplifications), we find
\begin{align*}
& \sum\limits_{k=0}^{n-2}\dbinom{n-2}{k}\left( 1+k\right) ^{k-1}\left( 1+\left(
\left( n-2\right) -k\right) \right) ^{\left( n-2\right) -k-1}\\
& =2\left( 2+\left( n-2\right) \right) ^{n-3}=2n^{n-3}.
\end{align*}
Hence,
\begin{align*}
2n^{n-3} & =\sum\limits_{k=0}^{n-2}\dbinom{n-2}{k}\left( 1+k\right) ^{k-1}\left(
1+\left( \left( n-2\right) -k\right) \right) ^{\left( n-2\right)
-k-1}\\
& =\sum\limits_{i=1}^{n-1}\dbinom{n-2}{i-1}\left( 1+\left( i-1\right) \right)
^{\left( i-1\right) -1}\left( 1+\left( \left( n-2\right) -\left(
i-1\right) \right) \right) ^{\left( n-2\right) -\left( i-1\right) -1}
\end{align*}
(here, we have substituted $i-1$ for $k$ in the sum). After some trivial
simplifications, this becomes
$$
2n^{n-3}=\sum\limits_{i=1}^{n-1}\dbinom{n-2}{i-1}i^{i-2}\left( n-i\right) ^{n-i-2}.
$$
Dividing this equality by $2$, we obtain the claim of Theorem 1. $\square$
Second proof: Cayley's formula and the symmetry of trees
Let me say right away that the above first proof of Theorem 1 is my favorite,
since it shows various rather general combinatorial identities in cascade. In
contrast, the following second proof is cute and memorable.
A tree shall here mean a simple undirected graph (i.e., a pair $\left(
V,E\right) $ in which $V$ is a finite set and $E$ is a set of $2$-element
subsets of $V$) that is connected and has no cycles. Of course, various other
equivalent characterizations of trees exist. If $n\in\mathbb{N}$, then an
$n$-tree means a tree whose vertex set is $\left\{ 1,2,\ldots,n\right\} $.
Notice that there exist no $0$-trees, since a graph with no vertices is not
connected. If $G=\left( V,E\right) $ is a simple undirected graph, then the
edge set $E$ is denoted by $\operatorname*{E}\left( G\right) $.
The following theorem is one of the famous results of 19th century
combinatorics -- the Cayley
formula (actually
discovered by Borchardt in 1860):
Theorem 5. Let $n$ be a positive integer. Then, the number of all
$n$-trees is $n^{n-2}$.
The similarity of the $n^{n-2}$ term here with the powers in Theorem 1
suggests a relation, and such indeed exists. First, let me derive a corollary
of Theorem 5:
Corollary 6. Let $n\geq2$ be an integer. Let $f$ be a $2$-element subset
of $\left\{ 1,2,\ldots,n\right\} $. Then, the number of all $n$-trees $T$
such that $f\in\operatorname*{E}\left( T\right) $ is $2n^{n-3}$.
Proof of Corollary 6. It is well-known that the number of edges in a tree is
always its number of vertices minus $1$. Thus, a tree with $n$ vertices must
have exactly $n-1$ edges. In other words, any $n$-tree must have exactly $n-1$ edges.
Let $F$ be the set of all $2$-element subsets of $\left\{ 1,2,\ldots
,n\right\} $. Then, for each $n$-tree $T$, we have $\operatorname*{E}\left(
T\right) \subseteq F$ (that is, the edges of $T$ are elements of $F$). Also,
$f$ is a $2$-element subset of $\left\{ 1,2,\ldots,n\right\} $ and thus
belongs to $F$. Also, clearly, $\left\vert F\right\vert =\dbinom{n}{2}
=\dfrac{n\left( n-1\right) }{2}$.
Now, we claim that any $e\in F$ satisfies
\begin{align}
\left( \text{the number of all }n\text{-trees }T\text{ such that }\left\{
1,2\right\} \in\operatorname*{E}\left( T\right) \right) \nonumber\\
\tag{3}
=\left( \text{the number of all }n\text{-trees }T\text{ such that }
e\in\operatorname*{E}\left( T\right) \right) .
\label{pf.c6.1}
\end{align}
[Proof of \eqref{pf.c6.1}: Let $e\in F$. Thus, $e$ is a $2$-element subset
of $\left\{ 1,2,\ldots,n\right\} $. In other words, $e=\left\{ x,y\right\}
$ for two distinct elements $x$ and $y$ of $\left\{ 1,2,\ldots,n\right\} $.
Consider these $x$ and $y$.
The elements $x$ and $y$ of $\left\{ 1,2,\ldots,n\right\} $ are distinct.
Thus, there exists some permutation $\sigma$ of $\left\{ 1,2,\ldots
,n\right\} $ such that $\sigma\left( 1\right) =x$ and $\sigma\left(
2\right) =y$. (For example, one can find such a permutation $\sigma$ by
setting its first two values $\sigma\left( 1\right) $ and $\sigma\left(
2\right) $ to be $x$ and $y$, and setting all its remaining $n-2$ values to
be the remaining $n-2$ elements of $\left\{ 1,2,\ldots,n\right\} $ in any
order.) Consider such a $\sigma$.
Recall that any permutation $\omega$ of $\left\{ 1,2,\ldots,n\right\} $ also
induces a permutation of the set $F$ of all $2$-element subsets of $\left\{
1,2,\ldots,n\right\} $ (namely, it sends each $g\in F$ to $\omega\left( g \right) =\left\{ \omega\left( u\right) \ \mid\ u\in g \right\} $). In
particular, $\sigma$ induces a permutation of the set $F$. This permutation
satisfies $\sigma\left( \left\{ 1,2\right\} \right) =\left\{
\underbrace{\sigma\left( 1\right) }_{=x},\underbrace{\sigma\left( 2\right)
}_{=y}\right\} =\left\{ x,y\right\} =e$.
If $T$ is an $n$-tree, and if $\omega$ is a permutation of $\left\{
1,2,\ldots,n\right\} $, then $\omega\left( T\right) $ shall denote the
$n$-tree whose edges are the images of the edges of $T$ under $\omega$ (that
is, $\operatorname*{E}\left( \omega\left( T\right) \right) =\left\{
\omega\left( e\right) \ \mid\ e\in\operatorname*{E}\left( T\right)
\right\} $). It is easy to see that this $\omega\left( T\right) $ is indeed
an $n$-tree (indeed, it is just the $n$-tree $T$ with its vertices relabelled
by the map $\omega$). Hence, the map
$$
\left\{ n\text{-trees}\right\} \rightarrow\left\{ n\text{-trees}\right\}
,\ T\mapsto\sigma\left( T\right)
$$
is well-defined. Moreover, this map is a bijection (indeed, the map $\left\{
n\text{-trees}\right\} \rightarrow\left\{ n\text{-trees}\right\}
,\ T\mapsto\sigma^{-1}\left( T\right) $ is easily seen to be inverse to it).
This bijection restricts to a bijection
\begin{align*}
\left\{ n\text{-trees }T\text{ such that }\left\{ 1,2\right\}
\in\operatorname*{E}\left( T\right) \right\} & \rightarrow\left\{
n\text{-trees }T\text{ such that }e\in\operatorname*{E}\left( T\right)
\right\} ,\\
T & \mapsto\sigma\left( T\right)
\end{align*}
(since $\sigma\left( \left\{ 1,2\right\} \right) =e$). Hence, the sets
$\left\{ n\text{-trees }T\text{ such that }\left\{ 1,2\right\}
\in\operatorname*{E}\left( T\right) \right\} $ and $\left\{ n\text{-trees
}T\text{ such that }e\in\operatorname*{E}\left( T\right) \right\} $ are in
bijection. Thus, these two sets have the same size. In other words,
\eqref{pf.c6.1} holds.]
Now,
\begin{align*}
& \left( \text{the number of all pairs }\left( T,e\right) \text{ where
}T\text{ is an }n\text{-tree and }e\in\operatorname*{E}\left( T\right)
\right) \\
& =\sum\limits_{T\text{ is an }n\text{-tree}}\underbrace{\left( \text{the number of
all }e\in\operatorname*{E}\left( T\right) \right) }_{\substack{=\left\vert
\operatorname*{E}\left( T\right) \right\vert =\left( \text{the number of
all edges of }T\right) =n-1\\\text{(since any }n\text{-tree must have exactly
}n-1\text{ edges)}}}\\
& =\sum\limits_{T\text{ is an }n\text{-tree}}\left( n-1\right) =\left( n-1\right)
\cdot\underbrace{\left( \text{the number of all }n\text{-trees}\right)
}_{\substack{=n^{n-2}\\\text{(by Theorem 5)}}}\\
& =\left( n-1\right) \cdot n^{n-2}.
\end{align*}
Hence,
\begin{align*}
& \left( n-1\right) \cdot n^{n-2}\\
& =\left( \text{the number of all pairs }\left( T,e\right) \text{ where
}T\text{ is an }n\text{-tree and }e\in\operatorname*{E}\left( T\right)
\right) \\
& =\sum\limits_{e\in F}\underbrace{\left( \text{the number of all }n\text{-trees
}T\text{ such that }e\in\operatorname*{E}\left( T\right) \right)
}_{\substack{=\left( \text{the number of all }n\text{-trees }T\text{ such
that }\left\{ 1,2\right\} \in\operatorname*{E}\left( T\right) \right)
\\\text{(by \eqref{pf.c6.1})}}}\\
& \ \ \ \ \ \ \ \ \ \ \left( \text{since }\operatorname*{E}\left( T\right)
\subseteq F\text{ for each }n\text{-tree }T\right) \\
& =\sum\limits_{e\in F}\left( \text{the number of all }n\text{-trees }T\text{ such
that }\left\{ 1,2\right\} \in\operatorname*{E}\left( T\right) \right) \\
& =\underbrace{\left\vert F\right\vert }_{=\dfrac{n\left( n-1\right) }{2}
} \cdot \underbrace{\left( \text{the number
of all }n\text{-trees }T\text{ such that }\left\{ 1,2\right\} \in
\operatorname*{E}\left( T\right) \right) }_{\substack{=\left( \text{the
number of all }n\text{-trees }T\text{ such that }f\in\operatorname*{E}\left(
T\right) \right) \\\text{(by \eqref{pf.c6.1}, applied to }e=f\text{)}}}\\
& =\dfrac{n\left( n-1\right) }{2}\cdot\left( \text{the number of all
}n\text{-trees }T\text{ such that }f\in\operatorname*{E}\left( T\right)
\right) .
\end{align*}
Solving this equality for $\left( \text{the number of all }n\text{-trees
}T\text{ such that }f\in\operatorname*{E}\left( T\right) \right) $, we
obtain
\begin{align*}
\left( \text{the number of all }n\text{-trees }T\text{ such that }
f\in\operatorname*{E}\left( T\right) \right) & =\left( n-1\right) \cdot
n^{n-2}/\dfrac{n\left( n-1\right) }{2}\\
& =2n^{n-3}.
\end{align*}
This proves Corollary 6. $\square$
Here is another trivial corollary of Theorem 5:
Corollary 7. Let $S$ be a finite nonempty set. Then, the number of all
trees with vertex set $S$ is $\left\vert S\right\vert ^{\left\vert
S\right\vert -2}$.
Proof of Corollary 7. Let $n=\left\vert S\right\vert $. Then, there exists a
bijection $\left\{ 1,2,\ldots,n\right\} \rightarrow S$. We can use this
bijection to transform any $n$-tree into a tree with vertex set $S$ (by
relabelling its vertices) and vice versa. Hence, the number of all trees with
vertex set $S$ equals the number of all $n$-trees. But the latter number is
$n^{n-2}$ (by Theorem 5). Hence, the former number is also $n^{n-2}$. In other
words, the number of all trees with vertex set $S$ is $n^{n-2}=\left\vert
S\right\vert ^{\left\vert S\right\vert -2}$ (since $n=\left\vert S\right\vert
$). Corollary 7 is proven. $\square$
Now, we can finally reprove Theorem 1:
Second proof of Theorem 1. Corollary 6 (applied to $f=\left\{ 1,2\right\}
$) shows that the number of all $n$-trees $T$ satisfying $\left\{
1,2\right\} \in\operatorname*{E}\left( T\right) $ is $2n^{n-3}$.
Now, let me show a different way to compute this number.
Indeed, if we remove the edge $\left\{ 1,2\right\} $ from an $n$-tree $T$
satisfying $\left\{ 1,2\right\} \in\operatorname*{E}\left( T\right) $,
then the remaining graph splits into two connected components, one of which
contains the vertex $1$ while the other contains the vertex $2$. Both
connected components are trees; we denote them by $A_{T}$ and $B_{T}$,
respectively (so that $1$ is a vertex of $A_{T}$ and $2$ is a vertex of
$B_{T}$). Let $\mathcal{A}_{T}$ be the vertex set of the tree $A_{T}$, and let
$\mathcal{B}_{T}$ be the vertex set of the tree $B_{T}$. Then, $\mathcal{A}
_{T}$ and $\mathcal{B}_{T}$ are two disjoint subsets of $\left\{
1,2,\ldots,n\right\} $ whose union is $\left\{ 1,2,\ldots,n\right\} $;
thus, $\mathcal{B}_{T}=\left\{ 1,2,\ldots,n\right\} \setminus\mathcal{A}
_{T}$. Note that $1\in\mathcal{A}_{T}$ (since $1$ is a vertex of $A_{T}$) and
$2\in\mathcal{B}_{T}$ (since $2$ is a vertex of $B_{T}$), thus $2\in
\mathcal{B}_{T}=\left\{ 1,2,\ldots,n\right\} \setminus\mathcal{A}_{T}$, thus
$2\notin\mathcal{A}_{T}$.
Obviously, an $n$-tree $T$ satisfying $\left\{ 1,2\right\} \in
\operatorname*{E}\left( T\right) $ is uniquely determined by the two trees
$A_{T}$ and $B_{T}$. Thus, any $n$-tree $T$ satisfying $\left\{ 1,2\right\}
\in\operatorname*{E}\left( T\right) $ can be constructed by the following procedure:
First, we decide how many elements the set $\mathcal{A}_{T}$ will have
(i.e., how many vertices $A_{T}$ will have). The number of elements of
$\mathcal{A}_{T}$ has to be an integer from $1$ to $n-1$ (in fact, it cannot
be $0$ (since we must have $1\in\mathcal{A}_{T}$); but it cannot be $n$ either
(since we must have $2\notin\mathcal{A}_{T}$)). We choose one such integer,
and denote it by $i$. We thus want the set $\mathcal{A}_{T}$ to have $i$ elements.
Then, we choose the set $\mathcal{A}_{T}$ itself (i.e., we decide which
vertices $A_{T}$ will have). We already know that this set will have $i$
elements, and we know that $1$ will be one of them (since $1\in\mathcal{A}
_{T}$) but $2$ will be not (since $2\notin\mathcal{A}_{T}$); thus, we are left
to choose the remaining $i-1$ elements of $\mathcal{A}_{T}$ freely among the
$n-2$ numbers $3,4,\ldots,n$. There are $\dbinom{n-2}{i-1}$ ways to make this choice.
Having chosen the set $\mathcal{A}_{T}$, we immediately know the set
$\mathcal{B}_{T}$: namely, $\mathcal{B}_{T}=\left\{ 1,2,\ldots,n\right\}
\setminus\mathcal{A}_{T}$ (there are no choices to make here). Notice that
$\left\vert \mathcal{A}_{T}\right\vert =i$ (since the set $\mathcal{A}_{T}$
has $i$ elements), and from $\mathcal{B}_{T}=\left\{ 1,2,\ldots,n\right\}
\setminus\mathcal{A}_{T}$ we obtain $\left\vert \mathcal{B}_{T}\right\vert
=\left\vert \left\{ 1,2,\ldots,n\right\} \setminus\mathcal{A}_{T}\right\vert
=\underbrace{\left\vert \left\{ 1,2,\ldots,n\right\} \right\vert }
_{=n}-\underbrace{\left\vert \mathcal{A}_{T}\right\vert }_{=i}=n-i$. Note that
both sets $\mathcal{A}_{T}$ and $\mathcal{B}_{T}$ are nonempty (since
$1\in\mathcal{A}_{T}$ but $2\in\mathcal{B}_{T}$ (since $2\notin\mathcal{A}
_{T}$)).
Now, we choose the tree $A_{T}$. This tree has to be a tree with vertex set
$\mathcal{A}_{T}$; the number of all such trees is $\left\vert \mathcal{A}
_{T}\right\vert ^{\left\vert \mathcal{A}_{T}\right\vert -2}$ (by Corollary 7,
applied to $S=\mathcal{A}_{T}$). In other words, the number of all such trees
is $i^{i-2}$ (since $\left\vert \mathcal{A}_{T}\right\vert =i$). Thus, there
are $i^{i-2}$ ways to choose $A_{T}$.
Now, we choose the tree $B_{T}$. This tree has to be a tree with vertex set
$\mathcal{B}_{T}$; the number of all such trees is $\left\vert \mathcal{B}
_{T}\right\vert ^{\left\vert \mathcal{B}_{T}\right\vert -2}$ (by Corollary 7,
applied to $S=\mathcal{B}_{T}$). In other words, the number of all such trees
is $\left( n-i\right) ^{n-i-2}$ (since $\left\vert \mathcal{B}
_{T}\right\vert =n-i$). Thus, there are $\left( n-i\right) ^{n-i-2}$ ways to
choose $B_{T}$.
Finally, we assemble the $n$-tree $T$ from $A_{T}$ and $B_{T}$ by adding
the edge $\left\{ 1,2\right\} $.
This procedure clearly yields any $n$-tree $T$ satisfying $\left\{
1,2\right\} \in\operatorname*{E}\left( T\right) $ in a unique way. Thus,
the number of all $n$-trees $T$ satisfying $\left\{ 1,2\right\}
\in\operatorname*{E}\left( T\right) $ is $\sum\limits_{i=1}^{n-1}\dbinom{n-2}
{i-1}i^{i-2}\left( n-i\right) ^{n-i-2}$ (because this is how many ways we
have to make choices in the above procedure). Comparing this with the fact
that this number is $2n^{n-3}$ (as shown above), we conclude that
$$
2n^{n-3}=\sum\limits_{i=1}^{n-1}\dbinom{n-2}{i-1}i^{i-2}\left( n-i\right) ^{n-i-2}.
$$
Dividing this equality by $2$, we obtain the claim of Theorem 1. $\square$
