Paul Erdös a montré que sur un graphe complet de n sommets et pour n < 7, il est impossible de disposer de flèches de telle sorte qu'on puisse atteindre en une seule étape deux sommets quelconques à partir d'un troisième sommet.

On suppose que sept grandes villes françaises sont reliées entre elles par des routes à sens unique. Le problème consiste à flécher chaque route de telle sorte que pour deux villes quelconques on puisse en trouver une troisième permettent de rejoindre directement les deux autres.

Source : Martin Gardner - Pour la Science - mars 1980 - n° 31.

 Solution