Matematyka.pl

Witam,

Zakładam fakt: Każdy graf planarny posiada co najmniej trzy wierzchołki stopnia nie większego niż pięć.

Rozważmy grafy \(\displaystyle{ |V|> 6}\). Każdy mniejszy graf można pomalować za pomocą sześciu kolorów - to właśnie chcę udowodnić - że każdy planarny można pomalować za pomocą sześciu barw.

Weźmy więc taki graf i usuńmy z niego węzeł stopnia nie większego niż pięć. Taki graf ma poprawne malowanie za pomocą sześciu kolorów. Teraz przywróćmy ten węzeł. Ma połączenie z co najwyżej pięcioma wierzchołkami, więc istnieje kolor na, który można go pokolorować. I to koniec dowodu.

Czy to jest ok ? bo ten mój dowód wygląda dziwnie. Usuńmy, zobaczmy, przywróćmy, przekonajmy się.

Na moje oko jest OK. Dodałbym tylko w samym dowodzie, przy zdaniu "usuńmy węzeł stopnia nie większego niż 5", że można to zrobić, bo taki istnieje na mocy podanego wcześniej faktu (o ile jest prawdziwy, bo nie sprawdzałem).

Ogólnie wiele dowodów indukcyjnych na grafach po wierzchołkach przebiega w taki sposób - załóżmy, weźmy graf większy, wybierzmy (często dowolny) wierzchołek, taki graf bez wierzchołka spełnia zał. indukcyjne, więc rozważamy, jak graf wyglądał przed usunięciem i pokazujemy to, co chcemy.