  By revisiting the Kirchhoff's Matrix-Tree Theorem, we give an exact formula
for the number of spanning trees of a graph in terms of the quantum relative
entropy between the maximally mixed state and another state specifically
obtained from the graph. We use properties of the quantum relative entropy to
prove tight bounds for the number of spanning trees in terms of basic
parameters like degrees and number of vertices.
