Na planszy
zamalowano
punktów. Udowodnić, że dla
pewnego
można wskazać
zamalowanych punktów
tak aby
i
były w tym samym wierszu,
i
– w tej samej kolumnie,
i
znów
w tym samym wierszu itd.,
i
w tym samym
wierszu i wreszcie
i
w tej samej kolumnie (tak jak na
rysunku ).
Rozwiązanie
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