Jak się za to zabrać?
Niech \(\displaystyle{ G}\) będzie grafem planarnym mającym co najmniej 3 wierzchołki. Wykazać, że jeśli \(\displaystyle{ G}\) nie ma cykli długości \(\displaystyle{ 3}\), to \(\displaystyle{ \left| E()G\right| \le 2\left| V(G)\right|-4}\).
Graf planarny bez trójkątów
-
gardner
Graf planarny bez trójkątów
Dość trudne zadanie. Postaram się wytłumaczyć na tyle na ile umiem. Trzeba tutaj skorzystać
ze wzoru Eulera mówiącego o tym,że \(\displaystyle{ f=k-p +1}\) gdzie f to liczba regionów,k liczba krawędzi a p to liczba wierzchołków. Zachodzą również 2 nierówności dla grafów planarnych:
\(\displaystyle{ f\le \frac{2}{3}k}\)
\(\displaystyle{ k \le 3p -6}\)
Teraz wypadałoby je udowodnić tzn. najważniejsza będzie pierwsza. Może w skrócie:
każdy region jest ograniczony przez cykl,którego minimalna liczba krawędzi wynosi 3.
Jeśli przez \(\displaystyle{ r_{i}}\) oznaczymy sobie liczbę krawędzi i-tego regionu to suma tych krawędzi na pewno będzie \(\displaystyle{ \ge 3f}\).
Następnie każda krawędź występuje w granicy co najwyżej 2 regionów. Więc suma naszych
\(\displaystyle{ r_{i}\le 2k}\) Stąd mamy pierwszą nierówność. Teraz skoro każdy nasz cykl ma długość 4 trzeba podstawić ją zamiast 3 i wyprowadzić wzór,który będzie się trochę różnił od tej pierwszej
nierówności. Dalej używając tej drugiej której podałem i tożsamości na liczbę regionów twoja nierówność wyjdzie banalnie. W razie kłopotów pisz
ze wzoru Eulera mówiącego o tym,że \(\displaystyle{ f=k-p +1}\) gdzie f to liczba regionów,k liczba krawędzi a p to liczba wierzchołków. Zachodzą również 2 nierówności dla grafów planarnych:
\(\displaystyle{ f\le \frac{2}{3}k}\)
\(\displaystyle{ k \le 3p -6}\)
Teraz wypadałoby je udowodnić tzn. najważniejsza będzie pierwsza. Może w skrócie:
każdy region jest ograniczony przez cykl,którego minimalna liczba krawędzi wynosi 3.
Jeśli przez \(\displaystyle{ r_{i}}\) oznaczymy sobie liczbę krawędzi i-tego regionu to suma tych krawędzi na pewno będzie \(\displaystyle{ \ge 3f}\).
Następnie każda krawędź występuje w granicy co najwyżej 2 regionów. Więc suma naszych
\(\displaystyle{ r_{i}\le 2k}\) Stąd mamy pierwszą nierówność. Teraz skoro każdy nasz cykl ma długość 4 trzeba podstawić ją zamiast 3 i wyprowadzić wzór,który będzie się trochę różnił od tej pierwszej
nierówności. Dalej używając tej drugiej której podałem i tożsamości na liczbę regionów twoja nierówność wyjdzie banalnie. W razie kłopotów pisz