Enoncé

La réponse est : le graphe $2$.

Observons tout d’abord que c’est possible pour le graphe $2$ : il suffit de partir de $A$, de recouvrir tout le contour extérieur du graphe pour revenir en $A$ puis de recouvrir les deux diagonales pour arriver en $B$.

Montrons maintenant que c’est impossible pour les graphes $1$ et $3$. Cela est dû au fait qu’il doit nécessairement y avoir un nombre impair d’arêtes qui partent du sommet $B$.

En effet, quand on recouvre le graphe, à chaque fois que l’on passe par $B$ sans s’y arrêter, on recouvre exactement deux arêtes partant de $B$ et, comme on doit finir en $B$, cela rajoute une arête supplémentaire, ce qui nous donne bien un nombre impair d’arêtes partant de $B$. Or, pour les graphes $1$ et $3$, il y a respectivement deux et quatre arêtes partant de $B$, ce qui rend impossible le recouvrement.

Remarque : en utilisant le même raisonnement, on montre facilement qu’une condition nécessaire pour pouvoir recouvrir un graphe en partant de $A$, en arrivant en $B$, sans jamais lever le crayon ni passer deux fois par la même arête, est que des sommets $A$ et $B$, il parte un nombre impair d’arêtes et que de chacun des autres sommets, il parte un nombre pair d’arêtes.

Si, en revanche, on veut tracer le graphe en partant d’un sommet $A$ et en finissant au sommet $A$, il faut que de chaque sommet parte un nombre pair d’arêtes. Un célèbre théorème d’Euler affirme que ces conditions sont suffisantes.