Proszę o pomoc z narysowaniem grafu o 9 wierzchołkach i 15 krawędziach, który będzie: planarny (płaski), jednokreslny, dwudzielny i półhamiltonowski jednocześnie.Nie mam pomysłu jak taki graf narysować.. Jak podzielę go na dwa zbiory wierzchołków i łącze je tak, żeby się nie przecinały krawędzie to mam tylko 8 krawędzi i ni jak dodać kolejną żeby został planarny.Czy taki graf jest możliwy do narysowania?
-- 11 sty 2017, o 17:05 --
Wróciłam do zadania i po czasie udało mi się narysować graf, który chyba spełnia podane wyżej warunki. Bardzo proszę o sprawdzenie czy jest poprawny i czy spełnia jeszcze dodatkowe własności, które wypiszę niżej. Rysunek

1.
Planarny - ze wzoru Eulera

2. półhamiltonowski - ma ścieżkę Hamiltona, ale nie Hamiltona, bo nie posiada cyklu?

3. Jednokreślny - B-E--A-E-C-I-D-G-A-I-B-H-D-E-C-G
4. Dwudzielny - dwa zbiory wierzchołków

Czy jest/istnieje:
A.
Droga jednobieżna czyli droga Eulera? taka sama jak w punkcie 3?
B.
Graf płaski - niestety, ale nie potrafię go narysować
C. Zbiory wierzchołków dla dwóch rozłącznych antyklik: czyli takie jak w punkcie 4?
D.
Drzewo rozpinające :

E.
Liczba chromatyczna = 7
F.
Graf Eulera nie, bo nie ma cyklu Eulera (jest tylko ścieżka)
G.
Regularny - nie, bo wierzchołki mają różne stopnie: