Chordal 2-Connected Graphs and Spanning Trees

摘要

We present a transformation on a chordal 2-connected simple graph that decreases the number of spanning trees. Based on this transformation, we show that for positive integers n, m with n(n ? 1)/2 ≥ m ≥ 2n ? 3, the threshold graph Q_(n,m) having n vertices and m edges that consists of an (n ? k)-clique and k ? 1 vertices of degree 2 is the only graph with the fewest spanning trees among all 2-connected chordal graphs on n vertices and m edges.