Spanning Tree

Question

Determine the number of the spanning treess in the following graph ???

Answer 1

Number of Spanning Trees: 2911

This can be solved by Kirchoff's Matrix Tree Theorem :

1. Make a matrix. (Rows = Columns = Total Vertices)
    
2. For i != j , if i & j are adjacent vertices,
then M[i][j] = -1,

if not M[i][j] = 0

For i == j, M[i][j] = degree of vertex
    
3. Last, Calculate the co-factor for any element. The cofactor that you get is the total number of spanning trees for that graph.

 

 

Comments

Thanks for the explanation.