Summary: We consider the problem of subdividing a region into districts - formed by geographically contiguous sites - which are as homogeneous as possible with respect to a certain set of characteristics. One possible mathematical formulation is the following. Given a connected graph \(G\) in which a vector of characteristic is associated with each vertex, find a minimum inertia partition of the vertex-set of \(G\) into a prescribed number of connected clusters. We propose a heuristic approach based on the solution of a sequence of relaxed problems where \(G\) is replaced by one of its spanning trees. Numerical experiments on medium-large graphs arising from real-life applications show that our heuristic almost always yields partitions with smaller inertia than those generated by a well established ascending algorithm.