Graf losowo eulerowski

[tomek1172]

Mówimy, że grał eulerowski jest losowo eulerowskim względem wierzchołka \(\displaystyle{ v}\), jeśli rozpoczynając drogę w \(\displaystyle{ v}\) i przechodząc przez graf w dowolny sposób tak, aby żadnej krawędzi nie przejść dwukrotnie, otrzymamy w końcu cykl Eulera.

Podaj przykład grafu eulerowskiego, który nie jest losowo eulerowski względem żadnego wierzchołka.

[Mruczek]

Weźmy klikę \(\displaystyle{ K _{5}}\). Każdy wierzchołek ma stopień \(\displaystyle{ 4}\), parzysty, więc ten graf ma cykl Eulera. Przechodząc np. w taki sposób po wierzchołkach: \(\displaystyle{ A, B, C, A, D, E, A}\) z dowolnego wierzchołka nie dostajemy cyklu Eulera.