Given a graph \(G=(V,E)\), the minimum branch vertices problem (MBV) consists in finding a spanning tree \(T=(V,E')\) of \(G\) minimizing the number of vertices with degree greater than two. We consider a simple combinatorial lower bound for the problem from which we propose a decomposition approach to break down the problem into several smaller subproblems that are more tractable computationally and then recombine the obtained solutions to generate a solution to the original larger problem. We also propose effective constructive heuristics to the problem which take into consideration the problem structure in order to obtain good feasible solutions. Computational results show that our decomposition approach is very fast and can drastically reduce the size of the subproblems that have to be solved, allowing a branch-and-cut algorithm to perform much better than when used over the full original problem. The results also show that the proposed constructive heuristics are very rapid and generate very good quality solutions, outperforming other heuristics available in the literature in several situations.