Egy F fának 17 csúcsa van, és bármely csúcsának fokszáma 1 vagy 4. Legkevesebb hány élt kell F-be húzni ahhoz, hogy a keletkező gráfnak legyen Euler-örsétája? (F többféle is lehet! )

Jajmár…

Ha egy fának 17 csúcsa van, akkor 16 éle. Legyen az 1 fokszámú csúcsainak száma x, a 4 fokszámúaké y.

x + y = 17,

(1*x + 4*y)/2 = 16.

Ebből x = 12.

Egy gráfnak akkor van Euler-körsétája, ha minden csúcs fokszáma páros, azaz mind a 12 első fokú csúcshoz be kell húzni legalább 1-1 élt. Mivel egy él kettő csúcsot köt össze, ehhez legalább 6 él kell.

Semmi ördöngősség nincs ebben a feladatban.