number of spanning tree

Question

Consider a complete bipartite graph with ‘m’ and ‘n’ vertices. If m = 4, n = 4, then the number of spanning trees of graph are ________.

Comments

will be 8??

total no of vertices

---

4096

---

number of labelled spanning trees of complete bipartite graph $K_{m,n}$ is $m^{n-1}n^{m-1}$ . I learned that formula from a question. don't know how it came.

---

Are they talking about minimum spanning tree or just spanning tree

Answer 1

If G is complete Bipartite Graph ,then number of spanning tree in G are  

m=4,n=4 hence $4^{{3}} * 4^{3} => 4096$

https://ajc.maths.uq.edu.au/pdf/28/ajc_v28_p073.pdf This link has derivation on how to calculate spanning tree in bipartite graph using rooted spanning tree. 

Comments

that proof looks scary af :D

---

yes. :P

Answer 2

A complete bipartite graph is a graph where there are two sets of vertices, and every vertex in one set is connected to every vertex in the other set. The number of vertices in one set is denoted as 'm' and the number of vertices in the other set is denoted as 'n'.

In this problem, we are given that m = 4 and n = 4. The total number of vertices in the graph is m+n = 4+4 = 8.

The number of spanning trees of a complete bipartite graph with 'm' and 'n' vertices can be calculated using the formula: (m^(n-2)) * (n^(m-2))

In this case, the number of spanning trees of the graph is: (4^(4-2)) * (4^(4-2)) = 4^2 * 4^2 = 16 * 16 = 256

So, the number of spanning trees of the complete bipartite graph with 4 and 4 vertices is 256.

It is important to note that this formula works only for complete bipartite graph and not for any other type of graph.