Problème proposé par Jean Moreau de Saint Martin

Zig a été embauché par la Poste pour relever les boîtes aux lettres de tout un quartier, et en vue d'organiser sa tournée il examine le plan du quartier. Quartier loin d'être plan, car il abonde en dalles, passages, galeries, qui le parcourent à plusieurs niveaux. Zig reste perplexe devant la complexité de ce réseau, car de chaque boîte aux lettres on peut aller directement à au moins 8 autres.
Puce vient à son secours :"Faut-il te plaindre de cette abondance ? Peut-être a-t-on la possibilité, pour deux boîtes quelconques, de les relier par 8 itinéraires dont toutes les boîtes sont distinctes ?"
-"Euh..., oui'' répond Zig après un temps de réflexion.Et peut-être que tout ensemble de 9 boîtes inclut deux boîtes voisines ?
- C'est vrai aussi.
- Alors, je vais te montrer comment faire ta tournée en passant à chaque boîte une fois et une seule !''
Pouvez-vous dire comment fait Puce, qui ne connaît pas ce quartier ?

N.B. Le nombre de connexité h d'un graphe ("graphe h-connexe'') est le nombre minimum de chaînes reliant une paire quelconque de sommets, sans sommet commun sauf aux extrémités ; il faut que chaque sommet ait au moins h voisins, mais cela ne suffit pas, d'où la première question de Puce.
Propriété utile à connaître (théorème de Menger) : étant donné un graphe h-connexe, un sous-ensemble E de h sommets au moins, et un sommet X hors de E, il existe h chaînes reliant X à h des sommets de E et sans autre
sommet commun que X.

Jean Moreau de Saint-Martin a résolu le problème.