KöMaL - Középiskolai Matematikai és Fizikai Lapok
 English
Információ
A lap
Pontverseny
Cikkek
Hírek
Fórum

Rendelje meg a KöMaL-t!

VersenyVizsga portál

Kísérletek.hu

Matematika oktatási portál

B. 3949. For what values of the positive integer n is there a simple graph in which the degree of each vertex is at most n, and there are i vertices of degree i for all 1\lei\len?

(Suggested by G. Mészáros, Kemence)

(4 points)

Deadline expired on 15 December 2006.


Google Translation (Sorry, the solution is published in Hungarian only.)

Megoldás. A fokszámok n(n+1)/2 összege, lévén az élek számának kétszerese, páros szám kell legyen. Ezért szükséges, hogy az n szám 4-gyel osztva 0 vagy 3 maradékot adjon. Megmutatjuk, hogy ez a feltétel egyben elégséges is. Az n=3, illetve az n=4 esetben ilyen gráfot láthatunk a mellékelt ábrán. Már csak azt kell megmutatni, hogy ha valamely n-re találtunk egy megfelelő Gn gráfot, akkor n értékét 4-gyel növelve, tudunk konstruálni egy megfelelő Gn+4 gráfot. Ezt pedig úgy tehetjük meg, ha a először a Gn gráf mellé felvesszük a Kn+1, Kn+2, Kn+3 és Kn+4 teljes gráfokat rendre n+1, n+2, n+3, illetve n+4 csúcson úgy, hogy az öt gráf csúcshalmazai páronként diszjunktak legyenek, majd pedig a Kn+1 és Kn+4 gráfok összesen 2n+5 csúcsát egy-egy új él segítségével összepárosítjuk a Kn+2 és Kn+3 gráfok összesen 2n+5 csúcsával. (Tulajdonképpen már a G4 gráfot is megkaphatjuk ilyen módon a 0 szögpontú G0 üres gráfból.)


Statistics on problem B. 3949.
89 students sent a solution.
4 points:Aczél Gergely, Ágoston Tamás, Anda Roland, Aujeszky Tamás, Bartha Zsolt, Blázsik Zoltán, Blutman Kristóf László, Bock Lilla, Bodor Bertalan, Bogár 560 Péter, Csaba Ákos, Cseh Ágnes, Cséke Balázs, Éles András, Fonyó Dávid, Gévay Gábor, Gresits Iván, Grósz Dániel, Győrffy Lajos, Herber Máté, Honner Balázs, Károlyi Gergely, Kiss 243 Réka, Kiss 902 Melinda Flóra, Kornis Kristóf, Korom-Vellás Judit, Kunos Ádám, Kunovszki Péter, Kurgyis Eszter, Mészáros András, Nagy 314 Dániel, Paál Gergely, Papp 648 Pál András, Peregi Tamás, Salát Zsófia, Sárkány Lőrinc, Sümegi Károly, Szalkai Balázs, Szalóki Dávid, Szűcs Gergely, Tallián György, Tossenberger Anna, Tóth 222 Barnabás, Tóth 666 László Márton, Tóth 796 Balázs, Török Balázs, Vajsz Tibor, Varga 171 László, Wolosz János.
3 points:17 students.
2 points:18 students.
1 point:5 students.


  • Problems in Mathematics of KöMaL, November 2006

  • Támogatóink:   Ericsson   Cognex   Emberi Erőforrás Támogatáskezelő   Emberi Erőforrások Minisztériuma   Nemzeti Tehetség Program    
    MTA Energiatudományi Kutatóközpont   MTA Wigner Fizikai Kutatóközpont     Nemzeti
Kulturális Alap   ELTE   Morgan Stanley