Matematyka.pl

Witam, zadanie brzmi następująco:

Niech G będzie grafem prostym mającym co najmniej 11 wierzchołków i niech G* będzie jego dopełnieniem
Udowodnij, że oba grafy G i G* nie mogą być jednocześnie planarne.

Próbowałem z Tw. Eulera i korzystając z faktu, że każdy planarny graf prosty zawiera wierzchołek stopnia co najwyżej 5, ale nie wiem, jak dojść do rozwiązania.

Suma liczby krawędzi grafu \(\displaystyle{ |E|}\) i liczby krawędzi jego dopełnienia \(\displaystyle{ |E'|}\) to liczba krawędzi grafu pełnego \(\displaystyle{ K_{11}}\), czyli

\(\displaystyle{ |E|+|E'|=\binom{11}{2}=55}\).

W grafie planarnym zachodzi jednak:

\(\displaystyle{ |E|\le 3|V|-6}\) (łatwy wniosek z tw. Eulera wiążącego liczby krawędzi, wierzchołków i ścian grafu planarnego)

czyli w naszym przypadku:

\(\displaystyle{ |E|\le 27}\)

oraz

\(\displaystyle{ |E'|\le 27}\),

czego nie da się pogodzić z \(\displaystyle{ |E|+|E'|=55}\).

Dziękuję!