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