Hogyan bizonyítjuk, hogy bármely egyszerű gráfban van 2 olyan csúcs amelyek fokszáma megegyezik?

Skatulyaelvvel. Van a gráfnak n darab csúcsa. Az egy csúcsból kiinduló élek száma lehet 0, 1, 2, ... n-1. Ez n db. lehetőség, de a 0 és az n-1 egymást kizáró esetek, így már csak n-1 különböző fokszáma lehet az n csúcsnak: valamelyik fokszám legalább kétszer szerepel.

de jó bizonyítás. én is köszönöm a választ!

Tetszik.