Pousse-pousse sur un graphe - Lycée Guy Moquet (Chateaubriant)

Titre du sujet
Pousse-pousse sur un graphe
Établissement
Lycée Guy Moquet (Chateaubriant)
Année
2014-2015
Résumé
On considère un graphe avec n+1 sommets numérotés de 0 a n, tel que chaque sommet
du graphe soit relié a exactement 3 autres sommets. On prend n jetons, numérotés de
1 a n et on les places arbitrairement sur n sommets du graphe. Peut-on faire en sorte
de remettre chaque jeton sur le sommet de même numéro, en s'autorisant uniquement a
faire glisser un jeton sur une arrête vers un sommet vide ?