Matematyka.pl

Udowodnij, że jeśli graf planarny \(\displaystyle{ G}\) ma mniej niż 30 krawędzi, to \(\displaystyle{ G}\) zawiera wierzchołek stopnia \(\displaystyle{ \le 4}\).


Myślałem, żeby założyć, że \(\displaystyle{ G}\) ma mniej niż 30 krawędzi i wszystkie wierzchołki ma stopnia \(\displaystyle{ \ge 5}\) i doprowadzić do sprzeczności.

Z definicji grafu planarnego, istnieje wierzchołek stopnia co najwyżej 5, czyli w tym przypadku dokładnie 5.
Niestety dalej nie wiem co robić. Ktoś pomoże?

Ze wzoru Euler'a skorzystaj

A możesz powiedzieć coś więcej? Nie znam ani liczby wierzchołków, ani ścian

Eh zero inicjatywy u młodzieży - gdy ja byłem w Twoim wieku...

Ze wzoru Eulera :
\(\displaystyle{ m \le 3n - 6}\) , gdzie \(\displaystyle{ m}\) to liczba krawędzi, a \(\displaystyle{ n}\) liczba wierzchołków.
Dodatkowo zauważ, ze w dowolnym grafie \(\displaystyle{ \sum_{v}^{} deg(v) = 2 |E|}\)
(chyba się to nazywa lemat o uściskach dłoni).
Załóżmy, że \(\displaystyle{ m < 30 \wedge deg(v) \ge 5}\) dla wszystkich wierzchołków.
Wówczas dostajemy dwa oszacowania na \(\displaystyle{ 2m}\):
\(\displaystyle{ 5 \cdot n \le 2m \le 6n -12}\)

Zatem musi zachodzic \(\displaystyle{ n \ge 12}\) , ale wowczas...