Witam,
Mamy graf. I jest on nieskierowany, spójny. Ma 100 wierzchołków.
Ma taką własność: każdy podgraf ma wierzchołek (choć jeden) o takiej własności, że jego stopień to jest nie większy niż 10.
Udowodnić, że liczba wierzchołków stopnia co najmniej 30 jest mniejsza niż 66.
Zadanie z grafem
Otrzymałeś(aś) rozwiązanie do zamieszczonego zadania? - podziękuj autorowi rozwiązania! Kliknij
-
- Expert
- Posty: 6762
- Rejestracja: 19 mar 2011, 00:22
- Otrzymane podziękowania: 3034 razy
- Płeć:
Usuwamy z grafu wierzchołek stopnia \(\le 10\). Ubywa co najwyżej \(10\) krawędzi. W otrzymanym podgrafie znów mamy taki wierzchołek, usuwamy go itd. Cały graf ma zatem nie więcej niż \(100\cdot 10=1000\) krawędzi. Tymczasem \(66\) wierzchołków stopnia \(\ge 30\) to co najmniej \(\frac{1}{2}(66\cdot 30+34\cdot 1)=1007\) krawędzi.