a) Egy bárban 60 lány van. Minden lány 12 fiút ismer és minden fiú 15 lányt ismer. Az ismertségek kölcsönösek. Hány fiú van a bárban? Tudunk-e úgy fiú-lány párokat alkotni, hogy minden fiút egy ismerős lánnyal párosítunk?
b) Egy kiránduláson fényképet készítenek a résztvevőkről. Minden képen 4-en szerepelnek, és tudjuk, hogy mindenkiről legalább 4 kép készült. A kirándulás végén mindenki választhat egy képet. Igazoljuk, hogy biztosan mindenkinek jutni fog olyan kép, amin rajta van.
a) Egy bálon 10 fiú és 10 lány vesz részt. Minden lány legalább 6 fiút ismer és minden fiú is legalább 6 lányt. Az ismertségek kölcsönösek. A nyitótáncon mindenki ismerőssel szeretne táncolni. Bizonyítsuk be, hogy ez lehetséges.
b) Egy 12 csúcsú páros gráfban minden csúcs foka 3 vagy 4. Bizonyítsuk be, hogy van a gráfban teljes párosítás.
a) Egy bálon összesen 16-an vesznek részt. Minden lány vagy 4 vagy 5 fiút ismer és minden fiú is vagy 4 vagy 5 lányt. A nyitótáncon mindenki ismerőssel szeretne táncolni. Bizonyítsuk be, hogy ez lehetséges.
b) Egy páros gráf két pontosztálya A és B. Két pont akkor szomszédos, ha ebben a szomszédsági mátrixban az A-ban lévő pont sorának és a B-ben lévő pont oszlopának metszetében 1-es áll:
\( \begin{matrix} & b_1 & b_2 & b_3 & b_4 & b_5 & b_6 & b_7 \\ a_1 & 0 & 1 & 1 & 0 & 1 & 0 & 0 \\ a_2 & 1 & 1 & 0 & 1 & 0 & 1 & 0 \\ a_3 & 1 & 1 & 0 & 1 & 0 & 0 & 1 \\ a_4 & 0 & 0 & 1 & 1 & 1 & 1 & 1 \\ a_5 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \\ a_6 & 1 & 1 & 0 & 1 & 1 & 0 & 1 \\ a_7 & 1 & 0 & 1 & 0 & 1 & 1 & 1 \end{matrix} \)
Van-e a gráfban teljes párosítás?
c) Egy másik G páros gráf két pontosztálya A és B. Két pont akkor szomszédos, ha ebben a szomszédsági mátrixban az A-ban lévő pont sorának és a B-ben lévő pont oszlopának metszetében 1-es áll. Van-e G-ben teljes párosítás?
\( \begin{matrix} & b_1 & b_2 & b_3 & b_4 & b_5 & b_6 & b_7 \\a_1 & 1 & 0 & 0 & 1 & 0 & 0 & 0 \\a_2 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\a_3 & 1 & 0 & 0 & 1 & 0 & 1 & 1 \\a_4 & 1 & 0 & 1 & 1 & 0 & 1 & 0 \\a_5 & 0 & 0 & 1 & 0 & 0 & 1 & 0 \\a_6 & 0 & 0 & 0 & 1 & 0 & 1 & 0 \\a_7 & 1 & 1 & 0 & 0 & 1 & 1 & 1 \end{matrix} \)
Egy 20 csúcsú egyszerű páros gráfban minden fok 5 vagy 6. Mutassuk meg, hogy a gráfnak van teljes párosítása.
Egy bálon 12 lány és 666 fiú vesz részt. A szervezők így 12 (fiú-lány) párt szeretnének összeállítani a nyitótánchoz úgy, hogy mindenki ismerőssel táncoljon. Minden lány legalább 11 fiút ismer, a fiúk közül viszont mindenki legfeljebb 11 lányt ismer. Biztosan össze tudják-e állítani a szervezők a 12 párt?
Egy bálon 1001 lány és 1001 fiú vesz részt, mindenkinek legalább 500 ellenkező nemű ismerőse van. Biztosan össze lehet-e állítani 1001 olyan fiú-lány párt, ahol a párok tagjai ismerősök?
Egy G egyszerű, páros gráf mindkét színosztálya egyenként 999 pontot tartalmaz, az A színosztályban minden pont foka legalább 666, B-ben pedig legalább 333. Mutassuk meg, hogy G-nek van teljes párosítása.
Egy G egyszerű, páros gráf A színosztályában 99 csúcsa van, ezek bármelyikének a fokszáma legalább 33, de A-ban van 66 olyan csúcs, amelyek bármelyikének foka legalább 66. Sőt, A tartalmaz 33 olyan csúcsot is, amelyek mindegyikéből legalább 99 él indul. Mutassuk meg, hogy G-nek van A-t fedő párosítása.
