On considère un graphe non orienté dont les arêtes a sont munies d’une valuation réelle υ(a) qui peut, selon le contexte, représenter un poids, un coût, une longueur, etc. On cherche un graphe partiel (S, B) de qui soit un arbre et qui soit de valuation minimum (la valuation de (S, B) étant la somme des valuations des arêtes de B). Le fait que l’arbre cherché atteigne tous les sommets de est traduit par le terme couvrant ; c’est la raison pour laquelle on parle d’arbre couvrant et qu’une solution du problème s’appelle arbre couvrant de valuation minimum ou plus simplement arbre couvrant minimum (s’il n’y a pas d’ambiguïté, on dit même parfois arbre minimum).
Il est clair que le problème admet une (ou des) solution(s) si et seulement si le graphe est connexe ; nous supposerons dans toute la suite qu’il en est ainsi.
Supposons que les valuations de soient toutes strictement positives : on parle alors souvent de poids et le problème est connu aussi sous le nom de problème de l’arbre couvrant de poids minimum. Considérons alors un graphe partiel connexe de de valuation minimum. Si possédait un cycle, on pourrait enlever une quelconque arête de ce cycle sans déconnecter ; les valuations étant toutes positives, on diminuerait ainsi la valuation de , contradiction avec la minimalité de ; est donc sans cycle. En conséquence, si les valuations sont strictement positives, la recherche d’un graphe partiel connexe de valuation minimum est équivalente à la recherche d’un arbre couvrant minimum…