Grafy s neuzavřenými eulerovskými tahy

Charakterizujte všechny grafy, které mají (ne nutně uzavřený) eulerovský tah.

Řešení
Pokud má graf uzavřený eulerovský tah, potom je souvislý a má všechny vrcholy sudého stupně.

Pokud má graf otevřený eulerovský tah, pak je souvislý a má právě dva vrcholy lichého stupně – konkrétně první a poslední vrchol tahu, ostatní mají sudý stupeň.
Odpověď
Graf má eulerovský tah, pokud je souvislý a má nejvýše dva vrcholy lichého stupně.