Liczba regionów w grafie planarnym

[sinus alfa]

Jaka jest maksymalna liczba regionów w grafie planarnym o n wierzchołkach?

Wiadomo, że dla każdego grafu planarnego o k krawędziach i p wierzchołkach:

\(\displaystyle{ k \le 3p - 6}\)

Ponadto, dla każdego grafu planarnego o f regionach:

\(\displaystyle{ f = k - p + 2}\) (wzór Eulera)

Podstawiając mamy:

\(\displaystyle{ f \le 3p - 6 - p + 2 = 2p - 4}\)

Czyli odpowiedź to:

\(\displaystyle{ 2n-4}\)

?