Algorithms

To find the number of spanning trees using 2 methods:

1. If graph is complete, use n^n-2 formula
2. If graph is not complete, then use kirchhoff theorem.

Steps in Kirchoff’s Approach:

(i) Make an Adjacency matrix.

(ii) Replace all non-diagonal is by – 1.

(iii) Replace all diagonal zero’s by the degree of the corresponding vertex.

(iv) Co-factors of any element will give the number of spanning trees.  

Using the Kirchhoff theorem will take lot of time because the number of vertices are 9. 

So, we use brute force technique to solve the problem with the help of Kruskal’s algorithm.