Egy irányítatlan gráfnak 5 csomópontja és 9 éle van. A következő számsorozatok közül melyik lehet a gráf csúcsainak fokszáma?

Ha 9 éle van, akkor összesen mennyi lesz a fokszám, az összes csúcsot összeadva? Ezzel kidobtál kettőt.

Ha 5 csúcs van, és egyszerű gráfról van szó (azaz nincs többszörös és hurokél), akkor mennyi a maximális fokszám egy adott csúcsra? Ezzel kidobtad a maradékot.

A b és a c kapásból kizárható, ugyan is a fokszámok összege nem lehet páratlan.

(Mert ugye egy élnek 2 vége van, azaz +2-vel növeli az összes fokok számát.)

Azaz a válasz máris 2-re szűkült le.

Amúgy kezdj el rajzolgatni, ha máshogy nem megy. Rakj le 5 csomópontot és próbálj 9 élet behúzni úgy, hogy az adott feltételeket teljesítse.