科研之友
微信
新浪微博
Facebook
分享链接
摘要
Boesch's theorem says that "Suppose that a connected graph G has two non-adjacent 2-degree vertices u(1) and u(2). Then t(G) <= t(G/{u(1), u(2))), where t(G) is the number of spanning trees of G." In this paper, we generalize this theorem as follows: "Suppose that G is a connected graph of order at least 3, and that u(1) and u(2) are two vertices of degree m and n, respectively, in G. Then t(G) <= mn-m(0)(2)/m+n-2m(0) t (G/{u(1), u(2)}), where m(0) (>= 0) is the number of multiple edges between u(1) and u(2).
