An Application of Circuit Polynomials to the Counting of Spanning Trees in Graphs


E._J. Farrell, J._C. Grell


$t$ is shown that the number of spanning trees in a graph can be obtained from the circuit polynomial of an associated graph. From this, the number of spanning tress in a regular graph is shown to be obtainable from the characteristic polynomial of a node-deleted subgraph. Finally, Cayley's theorem for the number of labelled tress is derived.