# Domácí úkol 7.2 - nezdeg
Čím více hran existuje v grafu, tím menší může být velikost dané nezávislé množiny.
Proto předpokládejme, že všechny vrcholy mají stejný (nejvyšší) stupeň, čímž dostaneme spodní hranici velikosti nezávislé množiny.
Vyberu-li některý z vrcholů, automaticky vylučuji $\Delta(G)$ vrcholů, které mohu zařadit do množiny $V'$ (ty, které jsou s ním spojeny).
To znamená, že vybereme-li $n$ vrcholů, zahodíme $\Delta(G)*n$ vrcholů. Jinými slovy, z $\Delta(G)+1$ vrcholů jich vybereme $1$ a zahodíme $\Delta(G)$, což odpovídá operaci dělení (hodnotou $\Delta(G)+1$).
Je samozřejmě možné, že ne všechny vrcholy mají stupeň rovný $\Delta(G)$. V takovém případě při jejich vybrání zahodíme méně než $\Delta(G)$ vrcholů a zůstane jich více - nikdy méně - pro potenciální výběr do množiny $V'$, takže velikost této množiny může být pouze větší než odvozená (což odpovídá tomu, že jsem odvozoval dolní hranici).