text: Are you familiar with the matrix tree theorem ? See http://mathworld.wolfram.com/MatrixTreeTheorem.html .\n\nEdit: The matrix tree theorem does not restrict the form of the spanning tree beyond the fact that the trees must not be the same graph.