  The quadratic minimum spanning tree problem and its variations such as the
quadratic bottleneck spanning tree problem, the minimum spanning tree problem
with conflict pair constraints, and the bottleneck spanning tree problem with
conflict pair constraints are useful in modeling various real life
applications. All these problems are known to be NP-hard. In this paper, we
investigate these problems to obtain additional insights into the structure of
the problems and to identify possible demarcation between easy and hard special
cases. New polynomially solvable cases have been identified, as well as NP-hard
instances on very simple graphs. As a byproduct, we have a recursive formula
for counting the number of spanning trees on a $(k,n)$-accordion and a
characterization of matroids in the context of a quadratic objective function.
