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