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?
Graf planarny - dowód
-
- Użytkownik
- Posty: 177
- Rejestracja: 27 paź 2015, o 17:31
- Płeć: Mężczyzna
- Lokalizacja: Polska
- Podziękował: 16 razy
Re: Graf planarny - dowód
A możesz powiedzieć coś więcej? Nie znam ani liczby wierzchołków, ani ścian
- leg14
- Użytkownik
- Posty: 3132
- Rejestracja: 5 lis 2014, o 20:24
- Płeć: Mężczyzna
- Lokalizacja: Radom
- Podziękował: 154 razy
- Pomógł: 475 razy
Re: Graf planarny - dowód
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...
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...
Ukryta treść:
Ostatnio zmieniony 16 wrz 2018, o 14:15 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Pisz staranniej.
Powód: Pisz staranniej.