Az A. 848. feladat (2023. március)

A. 848. Legyen \(\displaystyle G\) egy síkgráf, amely egyben páros gráf is. Igaz-e mindig, hogy minden lapjához hozzárendelhetjük egy csúcsát úgy, hogy semelyik két laphoz ne rendeljük ugyanazt a csúcsot?

Javasolta: Matolcsi Dávid (Budapest)

(7 pont)

A beküldési határidő 2023. április 11-én LEJÁRT.

Abból, hogy \(\displaystyle G\) páros gráf, csak annyit használunk, hogy nincs benne háromszög.

Válasszuk ki \(\displaystyle G\) néhány lapját, és vizsgáljuk a csúcsaik és éleik által meghatározott \(\displaystyle G'\) gráfot.

Mondjuk azt, hogy \(\displaystyle G'\)-nek \(\displaystyle f\) darab lapja, \(\displaystyle e\) darab éle és \(\displaystyle v\) darab csúcsa van. Euler poliéder-tételéből következően \(\displaystyle f-e+v\ge 1\).

\(\displaystyle G'\) minden lapját legalább \(\displaystyle 4\) él határolja, de minden él legfeljebb két lapot határol, így \(\displaystyle 4f\le 2e\), azaz \(\displaystyle 2f\le e\).

Ezekből az következik, hogy \(\displaystyle v\ge f+1\).

Képezzünk egy páros gráfot az egyik oldalon \(\displaystyle G\) lapjai, a másik oldalon \(\displaystyle G\) csúcsai között. Azt kell belátnunk, hogy létezik egy teljes párosítása a lapoknak a csúcsokhoz. Hall tétele szerint ez pontosan akkor lehetséges, ha a lapok minden \(\displaystyle f\) elemű részhalmazára a hozzájuk tartozó csúcsokból legalább \(\displaystyle f\) van. Éppen ezt láttuk be az imént.

Statisztika:

15 dolgozat érkezett.
7 pontot kapott:	Diaconescu Tashi, Lovas Márton, Nádor Benedek, Németh Márton, Sida Li, Szakács Ábel, Varga Boldizsár, Wiener Anna.
5 pontot kapott:	1 versenyző.
4 pontot kapott:	3 versenyző.
0 pontot kapott:	3 versenyző.

A KöMaL 2023. márciusi matematika feladatai