The Gateway to Computer Science Excellence
+15 votes

Let $K_{n}$ be the complete graph on $n$ vertices labeled $\left\{1, 2,\dots ,n\right\}$ with $m=\frac{n (n - 1)}{2}$ edges. What is the number of spanning trees of $K_{n}$?

  1. $\frac{m}{n - 1}$
  2. $m^{n - 1}$
  3. $n^{n - 2}$
  4. $n^{n - 1}$
  5. None of the above.
in Graph Theory by Boss (30.8k points)
retagged by | 687 views
For the same question if it is asked rooted spanning tree then answer would  be $n^{n-1}$

2 Answers

+11 votes
Best answer

Answer will be (C) 

e.g. for $K_4$ no. of spanning tree will be $16$.

Number of Spanning trees of a Complete Graph $K_{n}$ is given by Cayley's theorem = $n^{n-2}.$

by Veteran (119k points)
edited by
can u plz derive it. i also know the formula but for the first time i thought of deriving it.. but can't get the logic
this may be hit and try. any logical way of thinking, there is not that much of time there. what i thought is.

every vertex will have 2 choices to choose , as there will be (n-1) edges. every internal node have the choice to select any 2. as internal node will be having two edges so (n-1) (n-2) choices, while the 2 starting and end edge have (n-1) choice.

but can't get the formula.
+10 votes

Number of Spanning trees of a Complete Graph Kis given by Cayley's theorem = NN-2

by (119 points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,365 answers
105,263 users