graf planarny -dowód

[manduka]

Każdy planarny graf prosty zawiera wierzchołek stopnia co najwyżej \(\displaystyle{ 5.}\)

Dowód: Bez straty ogólności możemy założyć , że nasz graf jest spójny i ma co najmniej \(\displaystyle{ 3}\) wierzchołki. Gdyby każdy wierzchołek miał stopień co najmniej \(\displaystyle{ 6}\) to mielibyśmy równość \(\displaystyle{ 6n \le 2m}\), gdzie \(\displaystyle{ n}\)- wierzchołki, \(\displaystyle{ m}\)-krawędzie.

Mógłby mi ktoś wyjaśnić z jakiej własności skorzystano aby otrzymać tę nierówność ?

[robertm19]

\(\displaystyle{ 2m=\sum_{i=1}^n deg(x_{n})}\) liczymy krawędzie wychodzące z kazdeo wierzchołka. A \(\displaystyle{ deg\ge 6}\)

[manduka]

dzięki, ale dlaczego akurat nierówność w tę stronę i skąd się wzięło to \(\displaystyle{ n}\) przy \(\displaystyle{ 6}\) ?
Czy mógłbyś to jeszcze trochę jaśniej wytłumaczyć ? Z góry dziękuje.

[robertm19]

\(\displaystyle{ 2m=\sum_{i=1}^n deg(x_{i}) \ge \sum_{i=1}^n 6=6n}\)
Nierówność jest taka bo każdy stopień jest większy od 6 lub równy.

[manduka]

dzięki wielkie