title: Spanning tree which minimizes the number of vertices connected to multiple edges?
body: <p>Is there an algorithm to find a spanning tree of an undirected graph which minimizes the number of vertices connected to more than one edge?</p>
  
  <p>For example, given a 4 x 4 grid graph, we want to find a spanning tree like that on the left (which has 7 vertices connected to more than one edge) rather than that on the right (which has 12):</p>
  
  <p><a href="https://i.stack.imgur.com/VjpTE.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/VjpTE.png" alt="4 x 4 grid graph"></a></p>
  
  <p><strong>Edit:</strong> Would this problem be simpler if we consider only planar graphs (or even only grid graphs)?</p>