UGC NET CSE | June 2006 | Part 2 | Question: 2

Question

For a complete graph with $N$ vertices, the total number of spanning trees is given by:

• A. $2N-1$
• B. $N^{N-1}$
• C. $N^{N-2}$
• D. $2N+1$

Comments

C is the correct answer.

Answer 1

A simple graph with $n$ vertex is called a complete graph$(K_n)$ if the degree of each vertex is $n-1$ means each vertex is attached to the remaining $n-1$ vertex.

For any complete graph $K_n$, the number of possible spanning trees is $N^{N-2}$.

1. Spanning tree for $K_n$
2. Wikipedia

So option $C$ is correct here.