Le nombre d'arêtes d'un arbre ne dépend que de son nombre de sommets. C'est une propriété qui sert de contrôle immédiat, et dont la réciproque est fausse.
Les situations
Un arbre compte douze sommets.
Un autre graphe compte douze sommets et onze arêtes, sans qu'on sache s'il est connexe.
Un troisième est connexe, avec douze sommets et dix-huit arêtes.
Objectif
Donner le nombre d'arêtes du premier, dire si le deuxième est forcément un arbre, puis compter les arêtes à retirer du troisième pour en extraire un arbre couvrant, et ses cycles indépendants.
Pièges
Un triangle accompagné d'une composante séparée donne aussi douze sommets et onze arêtes, sans être un arbre. Compter les arêtes ne suffit jamais : il faut savoir si le graphe tient d'un seul tenant.