Dans la section précédente, nous avons examiné deux conditions nécessaires pour qu'un graphe soit Eulérien. Mais nous n'avons pas encore de condition suffisante.
Établir des conditions suffisantes est considérablement plus difficile qu'établir des conditions nécessaires, la raison principale étant que les preuves par contradiction sont difficiles à appliquer.
En fait, pour établir des conditions suffisantes, un informaticien préfère une preuve constructive. Essentiellement, une telle preuve indiquera non seulement l'existence d'une chaîne Eulérienne, mais aussi une méthode pour en trouver une. L'informaticien peut alors traduire cette méthode en un algorithme et ultérieurement en un programme pour trouver une telle chaîne.
On s'aperçoit que la réunion des deux conditions nécessaires examinées dans la section précédente forme une condition suffisante. Sans preuve, voici le théorème final :
est Eulérien si et seulement si est connexe et le
nombre de ses sommets impairs est 
ou 
.