Problème proposé par Gilles Armand

Préambule
Soient trois îles représentées par trois sommets A, B, . Elles sont reliées par P, Q, R ponts qui sont autant d’arêtes reliant  deux sommets comme dans le schéma ci-dessous :
                                                                          
On suppose P et Q impairs de la forme P = 2p+1 et Q = 2q + 1 et R pair = 2r
On désigne par Nb(P,Q,R) le nombre de chemins possibles entre A et C passant une fois et une seule par chacun des P + Q + R ponts.
Q₁ Pour p = 1, calculer Nb(3,Q,R) en fonction de q et de r.

Le problème
On considère maintenant les îles et les 17 ponts de Hautes-Bruyères illustrés ci-après.
                                         
Q₂ Définir et représenter le graphe non orienté associé à ces îles, à ces 17 ponts et à la terre ferme.
Q₃ Est-il possible d’effectuer un parcours eulérien selon lequel on peut traverser chacun des 17 ponts en une seule promenade, une fois sur chaque pont avec un point de départ distinct du point d’arrivée ?
Si oui choisir un point de départ et recenser le nombre de parcours différents correspondants.
Q₄ Est-il possible d’effectuer un circuit eulérien selon lequel le point de départ et le point d’arrivée sont confondus ?

 Solution