Problem B. 4518. (February 2013)
B. 4518. Let n2 be an even number, and let 0<k<n be an integer. Find the smallest number e with the following property: If a simple graph on n points has at least e edges then it contains k pairwise edge-disjoint perfect matchings.
Suggested by P. Maga, Budapest
(5 pont)
Deadline expired on March 11, 2013.
Sorry, the solution is available only in Hungarian. Google translation
Megoldási ötlet: Teljes körmérkőzés.
Megoldás. Megmutatjuk hogy
Először konstruálunk egy gráfot, aminek e-1 éle van, és nem tartalmaz k éldiszjunkt teljes párosítást. Vegyünk egy n-1 csúcsú teljes gráfot (a csúcsai legyenek ), és még egy v0 csúcsot, amiből k-1 él indul ki (mondjuk v0-t kössük össze a csúcsokkal.) A kapott gráfnak éle van. Mivel v0 foka csak k-1, nem szerepelhet k éldiszjunkt párosításban.
Másodszor negmutatjuk, hogy ha egy tetszőleges n csúcsú G egyszerű gráfnak legalább e éle van, akkor tartalmaz k éldiszjunkt teljes párosítást. Egészítsük ki G-t teljes gráffá úgy, hogy behúzzuk a hiányzó éleket; ezek száma legfeljebb . Az új éleket jelöljük meg, mondjuk színezzük pirosra.
Ismert, hogy minden páros n-re az n csúcsú teljes gráf felbontható n-1 éldiszjunkt teljes párosításra. (Lásd a Gy. 2097. gyakorlat megoldását, KöMaL 1983. május, 215-217. oldal.) A n-1 teljes párosításból legfeljebb n-k-1 tartalmaz piros élt, mert legfeljebb ennyi a piros élek száma. Tehát a többi, legalább (n-1)-(n-k-1)=k párosításban nincs piros él, ezek mind részgráfjai G-nek.
A 2012/13. évi spanyol bajnokság menetrendje
Statistics:
35 students sent a solution. 5 points: Ágoston Péter, Baran Zsuzsanna, Csernák Tamás, Di Giovanni Márk, Fehér Zsombor, Havasi 0 Márton, Herczeg József, Janzer Barnabás, Janzer Olivér, Kúsz Ágnes, Maga Balázs, Mócsy Miklós, Nagy Gergely, Nagy-György Pál, Németh Gergely, Schwarcz Tamás, Seress Dániel, Tardos Jakab, Tossenberger Tamás, Venczel Tünde. 4 points: Katona Dániel. 3 points: 7 students. 2 points: 3 students. 1 point: 2 students. 0 point: 2 students.
Problems in Mathematics of KöMaL, February 2013