Maximizing spanning trees in almost complete graphs

We examine the family of graphs whose complements are a union of paths and cycles and develop a very simple algebraic technique for computing the number of spanning trees. With our algebra, we can obtain a simple proof of a result of Kel'mans that evening-out path lengths increases the number of spanning trees in the complement graph. We provide similar characterizations for cycles. The theorems that we develop enable us to characterize the graphs in this family with a maximum number of spanning trees.