Encadrer le nombre d'arêtes d'un graphe à douze sommets, puis compter ce qu'il faut retirer pour n'en garder qu'un arbre.

Un arbre est un graphe connexe sans cycle. C'est exactement le graphe connexe le plus économe en arêtes : en retirer une le déconnecte, en ajouter une crée un cycle.

Le graphe complet relie chaque paire de sommets exactement une fois.

Le nombre maximal d'arêtes se compte en paires de sommets, et non en couples : relier A à B et relier B à A sont la même arête.

Un arbre couvrant garde tous les sommets, pas seulement une partie : c'est ce qui distingue un arbre couvrant d'un simple sous-arbre.