Il peut y avoir plusieurs arborescences minimales de même poids ayant un nombre minimal de bords ; en particulier, si tous les poids de bord d'un graphique donné sont les mêmes, alors chaque arbre de ce graphique est minimal.
Un certain nombre de problèmes tirés de la théorie des graphiques sont appelés arbre à balayage minimal.