La Montagne bourbonnaise comporte un réseau de sentiers de randonnée pédestre qui relient entre eux 10 villages (v_i, i = 1,2,..,10) avec  les caractéristiques suivantes :
C₁ : deux villages  quelconques sont reliés par un sentier au plus,
C₂ : il n’y a pas de sentier qui relie un village à lui-même (absence de boucle),
C₃ : tout circuit de randonnée passe par cinq villages au moins,
C₄ : deux sentiers distincts ne se rencontrent jamais en dehors des villages.

Q₁ Le réseau contient le plus grand nombre possible s₁ de sentiers compatible avec ces quatre caractéristiques.
Déterminer s₁  et donner une représentation graphique du réseau correspondant R₁ qui rend maximum le nombre de circuits de randonnée distincts. Existe-t-il dans ce réseau R₁ un circuit qui passe par les dix villages sans traverser deux fois le même village?
Q₂ La Communauté de villages décide de reconfigurer le réseau de sentiers de sorte que deux sentiers distincts peuvent désormais se croiser en dehors des villages. Les trois premières caractéristiques C₁,C₂ et C₃ sont maintenues et dans tout circuit de randonnée passant par cinq villages au moins, on s'interdit de changer de sentier lorsque celui-ci croise un ou plusieurs autres sentiers. Déterminer le plus grand nombre possible s₂ de sentiers dans le nouveau réseau et donner une représentation graphique du réseau R₂ qui comporte le minimum de croisements. Comment peut-on passer de R₁ à R₂ avec le minimum de modifications?