For a complete graph with N vertices, the total number of spanning trees is…
2006
For a complete graph with N vertices, the total number of spanning trees is given by:
- A.
2N−1
- B.
NN−1
- C.
NN−2
- D.
2N+1
Attempted by 63 students.
Show answer & explanation
Correct answer: C
According to Cayley's Formula, the number of spanning trees in a complete graph with N vertices is given by $N^{N-2}$. This formula applies specifically to complete graphs where every pair of distinct vertices is connected by a unique edge.
A video solution is available for this question — log in and enroll to watch it.