Given a random unweighted tree with $n$ vertices, what would be an average minimal distance between two of its vertices?
To put it in a more formal way, let's denote the set of all trees with $n$ vertices as $T_n$ and minimal distance between nodes $i$ and $j$ in a tree $t$ as $d_t(i, j)$, then what would be the value of:
$$\frac{1}{n^n} \cdot \sum_{t\in T_n} \left(\sum_{i,j \in [0; n-1]} d_t(i,j)\right)$$
From the count of $n^{n-2}$, I take it you’re talking about labelled trees.
It doesn’t matter which pair of vertices we consider, so let’s consider the two with highest indices, $n$ and $n-1$, and let’s see what happens in the construction of the tree’s Prüfer sequence if these two vertices are at a distance $d$ from each other. We remove all leaves until we’re left with just these two vertices and the ones between them. From then on, none of the indices in the Prüfer sequence is $n$ or $n-1$, and all the remaining indices are different. Conversely, if at some point all remaining indices are different and none are $n$ or $n-1$, then all the vertices with those indices must be between $n$ and $n-1$. Thus, the average distance is
\begin{eqnarray} \mathsf E[d] &=& \sum_{k=0}^{n-2}\frac{n-2}n\cdot\frac{n-3}n\cdots\frac{n-2-(k-1)}n\cdot\frac{k+2}n\cdot(k+1) \\ &=& (n-2)!\sum_{k=0}^{n-2}\frac{n^{-(k+1)}(k+2)(k+1)}{(n-2-k)!} \\ &=& (n-2)!\sum_{j=0}^{n-2}\frac{n^{-(n-1-j)}(n-j)(n-1-j)}{j!} \\ &=& \frac{(n-2)!}{n^{n-1}}\sum_{j=0}^{n-2}\frac{n^j(n-j)(n-1-j)}{j!} \\ &=& \frac{(n-2)!}{n^{n-2}}\sum_{j=0}^{n-2}\frac{n^j}{j!} \\ &=& \sum_{k=0}^{n-2}\frac{(n-2)!}{n^k(n-2-k)!} \\ &=& 1+\frac{n-2}n+\frac{(n-2)(n-3)}{n^2}+\cdots \\ &\approx& 1+\exp\left(-\frac2n\right)+\exp\left(-\frac2n-\frac3n\right)+\cdots \\ &=& \sum_{k=0}^{n-2}\exp\left(-\frac{k^2+3k}{2n}\right) \\ &\approx& \int_{-\frac12}^\infty\exp\left(-\frac{k^2+3k}{2n}\right)\mathrm dk \\ &\approx& \sqrt{\frac{\pi n}2}-1\;. \end{eqnarray}
Here’s a table up to $n=6$:
\begin{array}{c|cc} n&2&3&4&5&6\\\hline \mathsf E[d]&1&\frac43&\frac{13}8&\frac{236}{125}&\frac{115}{54} \end{array}
Here’s a plot that compares the exact values up to $n=100$ with the asymptotic result. There error is of order $n^{-\frac12}$.