Załóżmy, że m i k są liczbami

[max123321]

Załóżmy, że \(\displaystyle{ m}\) i \(\displaystyle{ k}\) są takimi dodatnimi liczbami całkowitymi, że \(\displaystyle{ m \ge k+1}\). Definiujemy graf dwudzielny \(\displaystyle{ G=(V_1,V_2,E)}\), którego wierzchołkami są pewne podzbiory zbioru \(\displaystyle{ \left[ 2m\right]}\), w następujący sposób:
\(\displaystyle{ V_1=\left\{ A \subseteq \left[ 2m\right]:\left| A\right|=k \right\}}\)
\(\displaystyle{ V_2=\left\{ B \subseteq \left[ 2m\right]:\left| B\right|=k+1 \right\}}\)
dla \(\displaystyle{ A \in V_1}\) oraz \(\displaystyle{ B \in V_2}\)
\(\displaystyle{ \left\{ A,B\right\} \in E \Leftrightarrow A \subseteq B}\).
Udowodnij, że w grafie \(\displaystyle{ G}\) istnieje skojarzenie pełne z \(\displaystyle{ V_1}\) do \(\displaystyle{ V_2}\).

Jak to zrobić?

[VirtualUser]

To zadanie to zastosowanie tw. Halla.
Ustalmy \(\displaystyle{ v_1 \in V_1}\). Jaki jest \(\displaystyle{ \deg(v_1)}\)?

[max123321]

Nie wiem, nie rozumiem tego zadania.

[MrCommando]

Czego w nim nie rozumiesz konkretnie?

Wierzchołek ze zbioru \(\displaystyle{ V_1}\) jest jakimś podzbiorem \(\displaystyle{ k}\)-elementowym \(\displaystyle{ [2m]}\). Pytanie o stopień równoważne jest pytaniu ile jest \(\displaystyle{ k+1}\)-elementowych podzbiorów \(\displaystyle{ [2m]}\) zawierających nasz poprzedni ustalony \(\displaystyle{ k}\)-elementowy.

[max123321]

Aha, bo krawędź pomiędzy wierzchołkami jest wtedy jak drugi zbiór zawiera pierwszy. No dobra, to coś mi zaczyna świtać chyba. To ten stopień to będzie \(\displaystyle{ 2m-k}\)?