KöMaL - Középiskolai Matematikai és Fizikai Lapok
Sign In
Sign Up
 Magyar
Information
Contest
Journal
Articles

 

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 11 March 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.

Our web pages are supported by:   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