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} \)
