Spanning Tree Count via Determinant

Problem

Count the spanning trees of a connected undirected graph using the Matrix-Tree theorem.

Build the Laplacian L = D - A, delete its last row and column, and return the determinant of the resulting (n-1) x (n-1) minor.

Hint

Cayley's formula says the complete graph on n vertices has n^(n-2) spanning trees.

case 1

in: [3,[[0,1],[1,2],[2,0]]]

expected: 3

case 2

in: [3,[[0,1],[1,2]]]

expected: 1

case 3

in: [4,[[0,1],[1,2],[2,3],[3,0]]]

expected: 4

case 4

in: [4,[[0,1],[0,2],[0,3],[1,2],[1,3],[2,3]]]

expected: 16

Starter codePython

def spanning_tree_count(num_vertices, edges):
    # Your code here
    pass

4 test cases · run your code against them in the editor