Kezdőlap


Feladat:	B.4742	Korcsoport: 18-	Nehézségi fok: átlagos
Megoldó(k):	Kővári Péter Viktor
Füzet:	2016/november, 472 - 473. oldal		PDF \| MathML
Témakör(ök):	Feladat, Teljesgráfok, Teljes indukció módszere
Hivatkozás(ok):	Feladatok: 2015/november: B.4742

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 $n = 3$ , 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

m

csúcsú teljes gráf éleire tudunk a feltételeknek megfelelően számokat írni és tekintsük az

m + 1

csúcsú

K_{m + 1}

teljes gráfot. Válasszuk ki

K_{m + 1}

-nek egy

m

csúcsú teljes

K_{m}

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

C

K_{m + 1}

-nek az a csúcsa, mely nincs benne

K_{m}

-ben. A

C

-ből induló élekre a következő módon írjuk a számokat:

i)

K_{m}

-ben nincs olyan csúcs, melyhez a

3^{m - 1}

szorzat tartozik (azaz bármely csúcshoz van olyan abba befutó él, melyre nem a

3

-as szám van írva), akkor mind az

m

darab

C

-ből kiinduló élre írjunk

3

-ast (2. ábra). Ekkor

K_{m + 1}

-ben a

C

-hez tartozó szorzat

3^{m}

, a

K_{m}

csúcsaihoz tartozó szorzatok közül pedig mindegyik kisebb, mint

3^{m}

, és közülük semelyik kettő sem egyezik meg, mert a csúcsokhoz

K_{m}

-ben különböző szorzatok tartoztak és a

C

-ből induló élekre írt számok beszámításával mindegyik szorzat

3

-szorosára nőtt.

2. ábra

i i)

K_{m}

-ben van olyan csúcs, melyhez a

3^{m - 1}

szorzat tartozik (azaz az összes, abban a csúcsban talalkozó élre a

3

-as szám van írva), akkor mind a

k

darab

C

-ből kiinduló élre írjunk

1

-est (3. ábra). Ekkor

K_{m + 1}

-ben a

C

-hez tartozó szorzat

1

, a

K_{m}

csúcsaihoz tartozó szorzatok közül pedig mindegyik legalább

3

, és közülük semelyik kettő sem egyezik meg, mert a csúcsokhoz

K_{m}

-ben különböző szorzatok tartoztak és a

C

-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

(m + 1)

-re is, s így minden természetes számra is.

Megjegyzés. Eljárásunkból következik, hogy minden

m

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

m

é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.