graf - rysunek

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: