Tato úloha neprošla kontrolou správnosti.
Vrcholy stupně nejvýše 11
Úloha číslo: 4325
Dokažte, že v rovinném grafu má alespoň polovina vrcholů stupeň nejvýše 11.
Řešení
Pro grafy na nejvýše 2 vrcholech tvrzení evidentně platí. Pro spor předpokládejme, že existuje graf na \(n\ge 3\) vrcholech, v němž je aspoň polovina vrcholů stupně aspoň 12. Tehdy je součet všech stupňů alespoň \(12\cdot (n/2)=6n\). V grafu je tedy alespoň \(3n\) hran, což je ve sporu s horním odhadem \(3n-6\) pro počet hran rovinného grafu na aspoň 3 vrcholech,
