The Minimum Number of Branch Vertices Spanning Tree Problem is to minimize the number of vertices of degree greater than two in a spanning tree. We present a branch-and-cut algorithm based on an enforced Integer Programming formulation, which can solve many more instances than previous methods. Since the problem is NP-hard, very large instances cannot be solved exactly. For such cases, a new heuristic two-stage method that gives very good approximate solutions is developed. 
Exact and heuristic solutions for the Minimum Number of Branch Vertices Spanning Tree Problem