Based on the multi-criteria minimum spanning tree(MST) problem and the MIN-MAX degree minimum spanning tree problem, a special multi-criteria MIN-MAX degree MST problem was discussed, aiming to minimize both the maximum degree and the total weights of a spanning tree. A unique solution scheme was designed, trying to find the Hamilton path firstly and seeking the MIN-MAX degree MST afterwards, after analyzing the correlation between this particular vertex degree constraint and the Hamilton path. Depending on different initial conditions, an improved ant colony optimization algorithm was introduced to change the transition probability from the basic exponential to linear form if there was no Hamilton path in the network, so as to enhance the computing efficiency without affecting the solution quality. A corresponding solution scheme was designed and coded by Delphi, in view of the strategies proposed above. A number of numerical examples were tested, and the results show that the algorithm proposed is efficient and effective for multi-criteria MIN-MAX degree minimum spanning tree problems.