forum.zadania.info

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.

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.