Matematyka.pl

Mam takie zadanie muszę stwierdzić czy istnieje graf nieplanarny hamiltonowski, nieeulerowski którego maksymalny stopień wierzchołka jest \(\displaystyle{ \le 4}\), jeżeli tak to mam podać jego przykład, a jeżeli nie mam mam to uzasadnić.
Proszę o pomoc

\(\displaystyle{ K_{3,3}}\)?

Dziękuje za odpowiedź, czyli masz na myśli np. ten graf?

... h_K3,3.svg

on na pewno jest nieeulerowski, i według mnie jest hamiltonowski.

Co Ty o tym sądzisz?

Nie tylko według Ciebie jest hamiltonowski.. On jak najbardziej jest hamiltonowski.. Wystarczy znaleźć ścieżkę Hamiltona.. Do tego ma własności, które potrzebowałeś: \(\displaystyle{ deg(v)=3}\) dla każdego \(\displaystyle{ v}\) oraz jest nieplanarny.. Wynika to choćby z twierdzenia mówiącego, że graf jest planarny kiedy nie zawiera podgrafu \(\displaystyle{ K_{3,3} \ \hbox{i }K_5}\)