Nous avons vu Section 6.4 que pour qu'un graphe soit Eulérien, il doit être connexe et le nombre de ses sommets de degré impair doit être zéro ou deux (théorème 6.3).
Nous allons écrire une fonction eulerian(G) qui retourne 1 (vrai) si le graphe G est Eulérien et 0 (faux) sinon.
Nous disposons déjà de la fonction connected(G) pour déterminer
si le graphe est connexe. Si le graphe n'est pas connexe on peut immédiatement
renvoyer 0. Sinon, il ne reste plus qu'à examiner le nombre
de sommets impairs de G. On va les compter.
Dès qu'on en a compté strictement plus de 2 on peut renvoyer 0.
Si la boucle se termine sans qu'on ait renvoyé 1 alors
n contient le nombre total de sommets impairs
et on est sûr que n vaut 0 ou 2 puisque le nombre de
sommets impairs est forcément pair. Il suffit donc de
renvoyer 1.