  We investigate the tractability of a simple fusion of two fundamental
structures on graphs, a spanning tree and a perfect matching. Specifically, we
consider the following problem: given an edge-weighted graph, find a
minimum-weight spanning tree among those containing a perfect matching. On the
positive side, we design a simple greedy algorithm for the case when the graph
is complete (or complete bipartite) and the edge weights take at most two
values. On the negative side, the problem is NP-hard even when the graph is
complete (or complete bipartite) and the edge weights take at most three
values, or when the graph is cubic, planar, and bipartite and the edge weights
take at most two values.
  We also consider an interesting variant. We call a tree strongly balanced if
on one side of the bipartition of the vertex set with respect to the tree, all
but one of the vertices have degree $2$ and the remaining one is a leaf. This
property is a sufficient condition for a tree to have a perfect matching, which
enjoys an additional property. When the underlying graph is bipartite, strongly
balanced spanning trees can be written as matroid intersection, and this fact
was recently utilized to design an approximation algorithm for some kind of
connectivity augmentation problem. The natural question is its tractability in
nonbipartite graphs. As a negative answer, it turns out NP-hard to test whether
a given graph has a strongly balanced spanning tree or not even when the graph
is subcubic and planar.
