Grafy planarne

[mol_ksiazkowy]

Dla jakiego \(\displaystyle{ n}\) istnieje graf \(\displaystyle{ G}\) o \(\displaystyle{ n}\) wierzchołkach taki, że zarówno \(\displaystyle{ G}\) jak i uzupełnienie \(\displaystyle{ G}\) są planarne ?

[arek1357]

Jest takie kryterium planarności:

\(\displaystyle{ m \le 3n-6}\) gdzie \(\displaystyle{ m}\) - krawędzie, \(\displaystyle{ n}\) - wierzchołki

\(\displaystyle{ \overline{G}= {n \choose 2} -m }\)

Tyle ma krawędzi dopełnienie grafu \(\displaystyle{ G}\)

Czyli mamy:

\(\displaystyle{ \frac{n(n-1)}{2} -m \le 3n-6}\)

lub:

\(\displaystyle{ \frac{n(n-1)}{2} \le m+3n-6 \le 6n-12}\)

z tej nierówności wyjdzie:

\(\displaystyle{ n \le 10}\)

[mol_ksiazkowy]

I czy istnieje taki graf gdy \(\displaystyle{ n=10}\) ?