Ugrás a tartalomhoz

Új matematikai mozaik

Ambrus Gergely, Bárszi Gergely, Csikós Balázs, Frenkel Péter, Gács András, Gyárfás András, Hraskó András, Kiss Emil, Laczkovich Miklós, Lovász László, Montágh Balázs, Moussong Gábor, Pach János, Pelikán József, Recski András, Reiman István

Typotex

Reguláris gráfok

Reguláris gráfok

Bérczi, Gergely

Gács, András

Köszönet a Bolyai Farkas Ösztöndíj támogatásáért. 

Hraskó, András

Szőnyi, Tamás

Köszönet az Alapítvány a Felsőoktatásért és Kutatásért Magyary Zoltán ösztöndíja és az F030737 számú OTKA projekt támogatásáért 

1. Bevezető feladatok

A cikkben sok feladatot tűzünk ki abban a reményben, hogy az Olvasó elgondolkodik rajtuk. Azon feladatok megoldását, amelyek a legfontosabbak a továbbiak szempontjából, közvetlenül a kitűzést követően közöljük, a többi probléma megoldását pedig az utolsó fejezetre tettük.

1. feladat A Bergengóc Tudományos Akadémia minden tagja három másik taggal levelezik. Legalább hány tagja van az Akadémiának, ha nincs három olyan tag, akik közül mindenki mindenkivel levelezik?

1. ábra.

Válasszunk ki két egymással levelező tudóst! Legyenek ezek A 1 és B 1 , A 1 további levelezőtársai B 2 és B 3 , míg B 1 levelezőtársai A 2 és A 3 . Ha az eddig megnevezett tudósok között lennének azonosak, akkor lenne 3 olyan tudós, akik közül mindegyik mindegyikkel levelezne. A 6 említett tudós tehát mind különböző, így legalább 6 tagja van a Bergengóc Akadémiának.

Lehetséges, hogy nincs is több tagja, hiszen ha A 2 és B 2 , A 2 és B 3 , A 3 és B 2 , valamint A 3 és B 3 is levelezik egymással, akkor mindegyik tudós épp három másikkal levelezik és nincs három olyan tudós, akik közül mindegyik mindegyikkel levelezik.

2. ábra.

2. feladat Lehetséges-e, hogy pontosan 7 tagja van a Bergengóc Akadémiának?

Általánosítsuk az 1. feladatot a következőképpen:

3. feladat A Bergengóc Tudományos Akadémia minden tagja r másik taggal levelezik. Legalább hány tagja van az Akadémiának, ha nincs három olyan tag, akik közül mindenki mindenkivel levelezik?

Az általános eset megoldása alig különbözik az r = 3 esetben látottaktól. Teljesen hasonlóan bizonyítható, hogy a tagok száma legalább 2 r , és annyi lehet is, ha a tudósok két r -elemű csoportba sorolhatók, és két tudós pontosan akkor levelezik egymással, ha különböző csoportban vannak.

3. ábra.