Планарни графи

[ivailo_radev]

Здравейте, имам една задачка, която е много лесна, но нещо ми убягва и не мога да я докажа.
Задачата е следната:
Даден е планарен граф G=(V,E) и [tex]p \in R, 0\le p\le 100[/tex]. Да се докаже, че най-малко p процента от върховете в G са от степен по-малка от [tex]\frac{600}{100-p}[/tex]

Много ще съм благодарен, ако някой помогне. Може да не е цяло доказателство, а само идея или лека насока

[drago]

Допусни противното. Напиши го. Схематично ще звучи така: твърде много върхове имат твърде голяма степен. Означи общия брой върхове с n и докажи, че ребрата ще са повече от 3n-6. Това ще е противоречие с факта, че всеки планарен граф с n върха има не повече от 3n-6 ребра.
Ако има нещо неясно пиши.

[ivailo_radev]

Нещо ми убягва доказателството обаче. Аз го знам, че е така, виждам го... но доказателство Продължавам да мисля де

[drago]

Хайде да направим така: напиши ми тук отрицанието на даденото твърдение.

[ivailo_radev]

Мислех го цяла вечер и нищо не измислих. Значи не ми е никакъв проблем да докажа, че не може да има повече от 3n-6 ребра. Например ако имаме р=99, то тогава трябва да се докаже, че поне 99% от върховете имат степен по-ниска от 600/(100-99)=600. За да има поне един връх степен 600, трябва да имаме поне 601 върхове . Т.е. минималния ни брой става 601 върхове(т.е. 99% от 601, което е 594,99 върха, да имат степен по-ниска от 600), за които ще имаме не повече от 3.601-6=1797 ребра. Тогава не можем да имаме 2 върха със степен 600, защото за тях ни трябват минимум 602 върха и съответно ще ни се вдигне максималният брой ребра. И тук някъде се обърквам тотално Аз я виждам пред мен, че е решена, защото при 99% трябва да допусна, че има 601-594=5 върха със степен по-висока или равна на 600, което си го доказах, че е невъзможно, обаче не знам как да го изпиша