  We consider the polyhedral properties of two spanning tree problems with
additional constraints. In the first problem, it is required to find a tree
with a minimum sum of edge weights among all spanning trees with the number of
leaves less or equal a given value. In the second problem, an additional
constraint is the assumption that the degree of all vertices of the spanning
tree does not exceed a given value. The decision versions of both problems are
NP-complete.
  We consider the polytopes of these problems and their 1-skeletons. We prove
that in both cases it is a NP-complete problem to determine whether the
vertices of 1-skeleton are adjacent. Although it is possible to obtain a
superpolynomial lower bounds on the clique numbers of these graphs. These
values characterize the time complexity in a broad class of algorithms based on
linear comparisons. The results indicate a fundamental difference in
combinatorial and geometric properties between the considered problems and the
classical minimum spanning tree problem.
