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.
Udowodnij, że graf i jego dopełnienie nie mogą być planarne
-
- Użytkownik
- Posty: 1874
- Rejestracja: 4 paź 2008, o 02:13
- Płeć: Kobieta
- Lokalizacja: Lost Hope
- Podziękował: 28 razy
- Pomógł: 502 razy
Udowodnij, że graf i jego dopełnienie nie mogą być planarne
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}\).
\(\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}\).