graf planarny Krystek: czy graf o 6 wierzcholkach ,regularny stopnia 4 jest planarny?odpowiedz uzasadnij wiec krawedzie to |E|=6*4/2=12 stosujac wzor |E|<=3|V|−6 udowadniam ze graf jest planarny 12<=3*6−6 12<=12−prawda myslicie ze uzasadnienie jest poprawne?

jc: K₅ plus wierzchołek plus 2 krawędzie łączące 6 wierzchołek z jakimiś 2 innymi. Taki graf nie jest planarny. Gdzieś trzeba wykorzystać regularność stopnia 4.

Pytający: Mnie przekonuje rysunek. I mamy: (graf jest planarny ∧ |V|≥3) ⇒ (|E|≤3|V|−6) W drugą stroną implikacja nie zachodzi, co pokazał jc.

Bankier: o co tutaj chodzi?

Krystek: ok,dzięki za pomoc

jc: Wypadałoby jeszcze uzasadnić, że graf ośmiościanu foremnego jest jedynym grafem spełniającym warunki zadania lub pokazać, że inne grafy spełniające warunki zadania również są planarne.