Wikipedia:Reference desk/Archives/Mathematics/2009 March 11#number of spanning trees of K n-e

Hello.

I want to use Cayley's formula to show that the number of spanning trees in the labeled graph K_n-e is (n-2)n^n-3. Here e is any edge in K_n. Can someone point me in the right direction please. Equivalently I want to figure out the number of spanning trees involving the edge e.--Shahab (talk) 06:23, 11 March 2009 (UTC)

: You know there are $n^\{n-2\}$ spanning trees altogether. Choose one at random. What is the probability that it includes e? McKay (talk) 07:37, 11 March 2009 (UTC)

::$\backslash frac\{n-1\}\{\backslash frac\{n(n-1)\}\{2\}\}$. Now what?--Shahab (talk) 07:56, 11 March 2009 (UTC)OK I got it. Thanks for the tip. Cheers--Shahab (talk) 08:03, 11 March 2009 (UTC)