Delta mi!

Załóżmy, że graf ma wierzchołków, Zauważmy, że stopień każdego wierzchołka może wynosić Gdyby stopnie wszystkich wierzchołków były różne, to w szczególności istniałby wierzchołek o stopniu połączony krawędzią z każdym z pozostałych wierzchołków. Wtedy jednak nie mógłby istnieć wierzchołek o stopniu 0.

Pokolorujmy wierzchołki pajęczyny na czarno i biało w sposób pokazany na rysunku. Zauważmy, że pająk z pola białego zawsze przechodzi do czarnego i odwrotnie. Ponieważ pól białych jest więcej niż czarnych, żądana ścieżka nie istnieje.

W rozwiązaniu tego zadania odwołamy się do teorii grafów. Skorzystamy z powszechnie znanego i nietrudnego w dowodzie faktu: w dowolnym grafie prostym o wierzchołkach i krawędziach istnieje cykl. Przypomnijmy, że w grafie prostym nie ma podwójnych krawędzi ani pętli.

Dla dowodu nie wprost załóżmy, że usunięcie dowolnej z kolumn spowoduje powstanie tablicy o dwóch identycznych wierszach. Oznacza to, że dla każdej z kolumn istnieje para wierszy, która różni się między sobą tylko w tej kolumnie. Rozważmy więc graf, którego wierzchołkami są wiersze naszej tablicy i połączmy dwa wiersze krawędzią, jeżeli dla pewnej kolumny są one tymi wierszami, które różnią się tylko w niej. Jeśli dla pewnej kolumny istnieje więcej takich par wierszy, to wybierzmy z nich dowolną i tylko między nimi poprowadźmy krawędź w naszym grafie. Oczywiście, jedna para wierszy zostanie połączona krawędzią co najwyżej raz - nie może bowiem zdarzyć się sytuacja, w której dwa wiersze różnią się na tylko jednej pozycji dla dwóch różnych pozycji. Utworzona przez nas struktura jest więc -wierzchołkowym grafem prostym o krawędziach. Z przytoczonego wcześniej faktu wynika istnienie cyklu w tym grafie. Innymi słowy, istnieje ciąg wierszy o numerach o tej własności, że dla dowolnego wiersze oraz różnią się na dokładnie jednej pozycji (przyjmujemy, że ). Oznaczmy przez numer pozycji, na której różnią się wiersze o numerach i Każda kolejna para wierszy różni się już w innej kolumnie niż -ta. Począwszy więc od wiersza o numerze każdy następny wiersz w naszym ciągu zawiera tą samą liczbę na pozycji -tej. Ale wiersze oraz różnią się również w innej kolumnie niż -ta, a zatem wiersz zawiera liczbę na pozycji Otrzymana sprzeczność kończy rozwiązanie zadania.

Niech będzie grafem o wierzchołkach oznaczających wiersze i kolumny planszy. Krawędź pomiędzy wierszem a kolumną jest w wtedy i tylko wtedy, gdy punkt o współrzędnych jest zamalowany. Graf ma więc krawędzi. Jak wiadomo, jeśli graf o wierzchołkach nie ma cyklu, to ma co najwyżej krawędzi. Zatem zawiera cykl. Z definicji krawędzi w wynika, że będzie on parzystej długości i wyznaczone przez niego krawędzie to szukane punkty

Każdy pan musi znać jakąś panią, inaczej nie znajdzie partnerki. Każdych dwóch panów musi znać łącznie co najmniej dwie panie – jeśli znają tylko jedną, to jeden z nią zatańczy, a drugi zostanie bez pary. Każdych trzech panów musi znać łącznie co najmniej trzy panie i tak dalej, każdych  panów musi znać łącznie co najmniej  pań.

Czy jeśli powyższe warunki są spełnione, to już wystarczy i na pewno uczestnicy balu mogą dobrać się w pary? Tak, to właśnie orzeka twierdzenie Halla, którego dowód i zastosowania były tematem wykładu.