Arrange the following simple graphs based on number of spanning trees they have:
A. $K_3$ (Complete graph with 3 nodes)
B. $K_4$ (Complete graph with 4 nodes)
C. $K_{2,2}$ (Complete bipartite graph with 2 nodes in each partition)
D. $C_5$ (Cycle graph with 5 nodes)
🎥 Video solution / Text Solution of this question is given below:
Number of spanning trees:
For complete graph:
$\tau(K_n)=n^{n-2}$
A: $K_3 = 3^{1} = 3$
B: $K_4 = 4^{2} = 16$
For complete bipartite graph:
$\tau(K_{m,n}) = m^{n-1} n^{m-1}$
C: $K_{2,2} = 2^{1} \times 2^{1} = 4$
For cycle graph:
$\tau(C_n)=n$
D: $C_5 = 5$
Thus:
A = 3
C = 4
D = 5
B = 16
Increasing order:
A, C, D, B