The deletion-contraction method for counting the number of spanning trees of graphs

摘要

In this paper we will be concerned with some combinatorial methods that enable us to determine the number of spanning trees of a graph. Although these methods apply only to rather restricted classes of graphs, sometimes strikingly simple calculations reveal the number of spanning trees of seemingly complex graphs, we presented techniques to derive spanning trees recursions in graphs. Then, we gave the generalization for these techniques. Finally, making use of our results, we investigated the complexity of some new graphs.