Arrange the following simple graphs based on a number of spanning trees they have :

A. K [Complete Graph with 3 nodes] 3 B.K [Complete Graph with 4 nodes] 4 C.K (Complete bipartite graph of the 2 nodes 2,2 in each partition) D.C (Cycle graph of 5 nodes) 5

1. AA, B, C, D
2. BA, C, B, D
3. CA, C, D, B
4. DD, B, C, A

Pick an option to check yourself, or open the answer below.

Show answer & explanation

Correct answer: C. A, C, D, B

Explanation

K₃ has 3 spanning trees (n^(n−2)), K₂,₂ (a 4-cycle) has 4, C₅ has 5, and K₄ has 16. Increasing order: A, C, D, B.