Zadanie:
Na obrázku je znázornený plánik dediny (do každej križovatky vedie párny počet ciest). Úlohou poštára je každý deň prejsť všetkými ulicami mesta, pričom službu musí začať aj skončiť na pošte. Zistite, či je možné zvoliť takú trasu, aby poštár prešiel každou ulicou práve raz. Ak áno, navrhnite ju.

Riešenie:
Použijeme algoritmus Edmondsa a Johnsona. Jeho realizáciu zobrazujú nasledujúce obrázky.

Výsledok:
Výsledkom algoritmu je hľadaný uzavretý Eulerovský ťah:

,

Nájdený ťah nám určuje, v akom poradí má poštár prechádzať jednotlivé ulice (pozri obrázok dole).