Bonjour,
Je dois montrer que dans chaque graphe (non orienté) on peut couvrir les nœuds par moins que n chemins disjoints (ou n est le cardinal du plus grand ensemble indépendant du graphe).
Pour le montrer j'ai dit qu'il existe une partition du graphe en chemins dont les bouts forment un ensemble indépendant I (sinon on peut les relier et faire un seul chemin des deux chemins précédents). Puisque l'ensemble indépendant intercepte les chemins disjoints, le nombre de chemins vaut le cardinal de I et il y a donc il y a moins que n chemins.
Est-ce que le résonnement est juste ou je passe à côté de quelque chose?
Merci pour votre aide
-----
Envoyé par zaskzask 