W jaki sposób można określić, czy poniższy konkretny graf nieskierowany jest (lub nie jest) plenarny?
O grafie: składa się z dokładnie 8 wierzchołków oznaczonych kolejno: '1', '2', ..., '7', '8'. Lista jego łączeń jest następująca:
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 1
1 5
2 6
3 7
4 8
Widzimy zatem, że graf ten możemy narysować np. jako pewien ośmiokąt o czterech "przekątnych", które stanowią połączone wierzchołki 1 i 5, 2 i 6, 3 i 7, 4 i 8.
Mój pomysł: uważam, że graf nie jest plenarny. Uzasadnienie: zauważmy, że ten graf jest spójny, ponieważ jak doskonale widać 'dla każdej pary wierzchołków istnieje ścieżka, która je łączy' - oczywiście można w tym miejscu sprawdzić wszystkie pary wierzchołków i pokazać, że istnieje między nimi ścieżka. Skoro graf jest spójny, to użyjmy twierdzenia Eulera.
W tym miejscu niestety utknąłem. Co dalej powinienem zrobić? A może jednak graf jest plenarny i moje przypuszczenia są złe? Może jakiś inny dowód (niezwiązany ze spójnością) będzie lepszy?
Z góry dziękuję za pomoc.