Matematyka.pl

Niech \(\displaystyle{ \left[ 5\right]}\) będzie zbiorem dziewczyn. Niech \(\displaystyle{ {c_{1}, c_{2}, c_{3}, c_{4}, c_{5} }}\) będzie zbiorem chłopaków. Niech \(\displaystyle{ A _{i}}\) oznacza zbiór chłopaków którzy podobają się dziewczynie i, gdzie \(\displaystyle{ A_{i} = {c_{1} }, A_{2} = {c_{2} ,c_{3} }, A_{3} = { c_{1}, c_{2} }, A_{4} = {c_{1}, c_{3} }, A_{5} = { c_{1}, c_{4}, c_{5} }}\) Zbadać czy da się wszystkie dziewczyny wydać za mąż za chłopaków, którzy im się podobają tak, aby żaden chłopak nie był mężem więcej niż jednej dziewczyny.


Po narysowaniu grafu dwudzielnego to wszystko widać, ale jak to formalnie udowodnić?

Twierdzenie Halla mówi o tym w ścisły sposób, wystarczy sprawdzić jego założenia