Consider the Graph below: How many spanning trees can be found?

Key idea: Use the Matrix-Tree theorem: the number of spanning trees equals the determinant of any cofactor of the Laplacian matrix.

• Label the four vertices A, B, C, D. The edges are: A–B, B–C, A–D, B–D, C–D.

• Compute degrees: deg(A)=2, deg(B)=3, deg(C)=2, deg(D)=3.

• Form the Laplacian matrix L (rows/columns in order A, B, C, D):

  L = [ [2, -1, 0, -1], [-1, 3, -1, -1], [0, -1, 2, -1], [-1, -1, -1, 3] ]

• Delete the row and column for one vertex (delete D) to get the 3×3 minor M:

  M = [ [2, -1, 0], [-1, 3, -1], [0, -1, 2] ]

• Compute det(M) by expanding along the first row:

  det(M) = 2*det([[3,-1],[-1,2]]) - (-1)*det([[-1,-1],[0,2]])

  det(M) = 2*(3*2 - (-1)*(-1)) + 1*((-1)*2 - (-1)*0) = 2*(6 - 1) + 1*(-2) = 10 - 2 = 8.

• Conclusion: the number of spanning trees is 8.