K4 Spanning Trees Calculation

Cayley's formula provides the number of spanning trees for a complete graph $K_n$. The formula is $n^{n-2}$.

For the given complete graph $K_4$, we have $n=4$. Applying Cayley's formula:

$ \text{Number of spanning trees} = 4^{4-2} = 4^2 = 16 $

Thus, $K_4$ has 16 spanning trees.

K2,2 Bipartite Graph Spanning Trees

The number of spanning trees in a complete bipartite graph $K_{m,n}$ can be calculated using the formula $m^{n-1} n^{m-1}$.

For the given complete bipartite graph $K_{2,2}$, we have $m=2$ and $n=2$. Applying the formula:

$ \text{Number of spanning trees} = 2^{2-1} \times 2^{2-1} = 2^1 \times 2^1 = 2 \times 2 = 4 $

Alternatively, note that $K_{2,2}$ is the same as the cycle graph $C_4$. A cycle graph $C_n$ has $n$ spanning trees. For $C_4$, this means 4 spanning trees.

Graph Spanning Trees Summary

The calculation shows that $K_4$ has 16 spanning trees and $K_{2,2}$ has 4 spanning trees.

Therefore, the counts are 16 and 4, respectively.