Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
Already signed up?
New to KöMaL?

Problem B. 4518. (February 2013)

B. 4518. Let n\ge2 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


e = \binom{n-1}2+k.

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 v_1,\ldots,v_{n-1}), és még egy v0 csúcsot, amiből k-1 él indul ki (mondjuk v0-t kössük össze a v_1,\ldots,v_{k-1} csúcsokkal.) A kapott gráfnak \binom{n-1}2+k-1=e-1 é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 \binom{n}2-e=\binom{n}2-\binom{n-1}2-k = n-k-1. 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