On the question of counting spanning trees in labelled, nonplanar graphs

It is emphasized by means of counter-examples that the theorem of Gutman, Mallion and Essam (1983, Molec. Phys., 50, 859), for computing the number of spanning trees in a labelled graph, is generally valid only for planar graphs—i.e., those that may be embedded, without crossings, in a plane or on the surface of a sphere. The original matrix-tree theorem, by contrast, holds for all graphs. Therefore, whenever it is required to calculate the complexity of a nonplanar graph, the matrix-tree theorem, or some equivalent re-casting of it, should be used, and not the theorem of Gutman et al.—convenient as that latter theorem often is when a planar graph is being dealt with. Another approach which, like the matrix-tree theorem, is equally applicable to planar and nonplanar graphs, is signalled in the ‘Note Added in Proof’.