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. Megoldás. Az állítást a csúcsok száma szerinti teljes indukcióval bizonyítjuk. Ha , akkor írjunk a gráf három élére 1-et, 2-t és 3-at (1. ábra), ekkor az egyes csúcsokba befutó élekre írt számok szorzata rendre 2, 3 és 6.
1. ábra Tegyük fel, hogy az csúcsú teljes gráf éleire tudunk a feltételeknek megfelelően számokat írni és tekintsük az csúcsú teljes gráfot. Válasszuk ki -nek egy csúcsú teljes részgráfját és ennek éleire írjunk számokat úgy, hogy minden csúcsban különböző legyen az oda befutó élekre írt számok szorzata. Legyen a -nek az a csúcsa, mely nincs benne -ben. A -ből induló élekre a következő módon írjuk a számokat: Ha -ben nincs olyan csúcs, melyhez a szorzat tartozik (azaz bármely csúcshoz van olyan abba befutó él, melyre nem a -as szám van írva), akkor mind az darab -ből kiinduló élre írjunk -ast (2. ábra). Ekkor -ben a -hez tartozó szorzat , a csúcsaihoz tartozó szorzatok közül pedig mindegyik kisebb, mint , és közülük semelyik kettő sem egyezik meg, mert a csúcsokhoz -ben különböző szorzatok tartoztak és a -ből induló élekre írt számok beszámításával mindegyik szorzat -szorosára nőtt.
2. ábra Ha -ben van olyan csúcs, melyhez a szorzat tartozik (azaz az összes, abban a csúcsban talalkozó élre a -as szám van írva), akkor mind a darab -ből kiinduló élre írjunk -est (3. ábra). Ekkor -ben a -hez tartozó szorzat , a csúcsaihoz tartozó szorzatok közül pedig mindegyik legalább , és közülük semelyik kettő sem egyezik meg, mert a csúcsokhoz -ben különböző szorzatok tartoztak és a -ből induló élekre írt számok beszámításával a szorzatok nem változtak.
3. ábra Tehát az állítás igaz -re is, s így minden természetes számra is.
Megjegyzés. Eljárásunkból következik, hogy minden esetén a gráfnak csak egyetlen élére írunk 2-t, az összes többi élre 1-et vagy 3-at. Adódik a kérdés, hogy nem lehet-e bizonyos értékek esetén csak két különböző számot az élekre írva elérni, hogy minden csúcsban különböző legyen az oda befutó élekre írt számok szorzata? A válasz nem, s könnyű meggondolni, hogy ez következik abból az ismert tételből, mely szerint bármely véges, egyszerű gráfnak van két azonos fokszámú csúcsa.
|