OKTV 2020/2021 III. kategória 1. forduló 3. feladat
(Feladat azonosítója: OKTV_20202021_3k1f3f )
Témakör: *Kombinatorika

Egy egyszerű gráfban csúcsok egy halmazát függetlennek nevezzük, ha semelyik két eleme között nem fut él. Jelölje $ F(G) $ a $ G $ egyszerű gráf csúcsai közül kiválasztható független részhalmazok számát. Adott $ n $ mellett az $ n $ csúcsú összefüggő gráfok közül melyikre lesz $ F(G) $ maximális?



 

Megoldás:  

Csillaggráf