How many trees are there on $\{1,2,...,n\}$ vertices, such that vertices 1,2 are adjacent (there exists an edge between them)?
Hey all. I tried using prüfer sequences to find the exact number but I don't think this is the proper way to solve this. Would be happy to get some help on that problem, thanks in advance :)
By Cayley's formula, the total number of trees is $n^{n-2}$. Each has $n-1$ edges, but in the complete graph there are $\frac12n(n-1)$ edges in all. So the probability that a random tree has a given edge is thus $2/n$ and so $2n^{n-3}$ trees have the edge $1$-$2$.