Wikipedia:Reference desk/Archives/Mathematics/2009 March 11

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

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)

${\frac {n-1}{\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)