Do nearly balanced multigraphs have more spanning trees?
Ching‐Shui Cheng, Joseph C. Masaro, Chi Song Wong · Journal of Graph Theory · 1985
Abstract Letdithe degree of theith vertex of a mutigraph and λijbe the number of edges between vertexiand vertexj.A multigraph is called nearly balanced if |di−di| ≤1 for alli≠i′ and |λij−λij| for alliand allj,j′ Let be the collection of all the multigraphs withvvertices and e edges. It is shown that for anyv, there is ane* such that if, then any nearly balanced graph in ζv, ehas more spanning trees than any non‐nearly‐balanced graph in ζv, e.