Définition de graphe Eulérien

Dans cette section, nous allons préciser le concept de graphe ``Eulérien''.

Définition 6.1   Un graphe $G$ est Eulérien si et seulement il contient une chaîne $C = s_1, e_1, s_2, e_2, \ldots, s_m, e_m, s_{m+1}$ telle que
$\{s_1, s_2, \ldots, s_m, s_{m+1}\} = V(G)$, $\{e_1, e_2, \ldots, e_m\} = E(G)$ et $\vert E(G)\vert = m$.

Examinons les conséquences de cette définition. Sa signification est premièrement que
``si on trouve une telle chaîne, alors le graphe est Eulérien''
et deuxièmement que
``un graphe n'est Eulérien que s'il a une telle chaîne''.
En mathématique et en informatique, on utilise souvent l'abréviation ``ssi'' pour ``si et seulement si'' (de même en Anglais, la phrase ``if and only if'' est abrégée en ``iff'').

Puis, la définition nous dit que la chaîne doit avoir certaines propriétés : il faut que l'ensemble des sommets de la chaîne soit l'ensemble des sommets du graphe, autrement dit, la chaîne doit passer par tous les sommets du graphe. Remarquons qu'un graphe ayant un sommet isolé ne peut pas être Eulérien.

De même la chaîne doit passer par l'ensemble des arêtes. C'est la signification de l'expression $\{e_1, e_2, \ldots, e_m\} = E(G)$.

Finalement, il faut que $\vert E(G)\vert = m$, à savoir que le nombre total d'arêtes dans le graphe soit égal au nombre d'arêtes dans la chaîne. Autrement dit, la chaîne ne peut pas passer deux fois par la même arête. Une telle restriction n'existe pas pour les sommets.

En résumé, la définition veut dire ``un graphe est Eulérien si et seulement s'il contient une chaîne qui passe par tous les sommets et emprunte exactement une fois chacune des arêtes''.