Matematické Fórum

↑ Bakerstreet:

Ahoj, vyuzij toho, ze
a) v 5-souvislem grafu ma kazdy vrchol alespon 5 sousedu
b) v planarnim grafu plati  v >= 2+e/3

A postupuj pomoci iteraci:

1) Je-li graf 5-souvisly, musi mit alespon 6 vrcholu (vrchol+5 sousedu)
2) K6 neni planarni => graf musi mit alespon 7 vrcholu
3a) alespon 7 vrcholu + kazdy alespon 5 sousedu => alespon 7*5/2 = 17.5 hran => 18 hran
3b) alespon 18 hran + planarni graf => v >= 2+e/3 >=  2+18/3 = 8
4a) alespon 8 vrcholu + kazdy alespon 5 sousedu => alespon 8*5/2=20 hran
4b) alespon 20 hran + planarni graf => v >= 2+e/3 >= 2+20/3 = 8.66 => 9 vrcholu
.
.
.

Schvalne, kdy se ti iterace zastavi (zacykli).