The Kirchhoff's Matrix-Tree Theorem revisited: counting spanning trees   with the quantum relative entropy
  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. 
Vittorio Giovannetti, Simone Severini
quant-ph cs.IT math.CO math.IT