A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre. Egy fagráf bejárásának nevezzük a következőt: egy bábu az élek mentén lépkedve eljut minden csúcshoz, és minden élen pontosan kétszer megy végig. Két bábu egyszerre járja be a fát, ha egyszerre indulnak, esetleg különböző csúcsokból, és időegységenként egyet-egyet lépnek. Két bábu akkor találkozik, ha egyszerre lépnek ugyanarra a csúcsra, vagy egyszerre tartózkodnak ugyanazon az élen. Jelöljük -nel azt a legnagyobb számot, amelyre létezik olyan csúcsú fa, amit darab bábu egyszerre be tud járni úgy, hogy egyetlen találkozás sem történik. Bizonyítsuk be, hogy , ha pozitív egész. |