thumb|Ilustracja zagadki z książki Domki i studnie – zagadka matematyczna, której współczesna wersja może mieć następujące brzmienie:
Formalnie łamigłówka odpowiada na pytanie czy pełny graf dwudzielny jest płaski.
Historia Przegląd historii zagadki podał David E. Kullman w 1979 stwierdzając, że większość publikacji na temat tego problemu określa go jako „starożytny”. Najwcześniejszą wersję, którą odnalazł Kullman, opublikował Henry Ernest Dudeney w 1917. Tę samą zagadkę Dudeney opublikował wcześniej w 1913 w The Strand Magazine podkreślając, że jest ona bardzo stara, lecz ją uwspółcześnił dzięki zastosowaniu „wody, gazu i elektryczności”.
W innych starych wersjach zagadki należało wytyczyć ścieżki od trzech domów do trzech studni, kościoła, knajpy i studni lub gołębnika, studni i brogu.
Zagadka stała się motywacją w teorii grafów nad wprowadzeniem pojęcia grafu planarnego.
Rozwiązanie thumb|150px|Graf Nie istnieje rozwiązanie pozwalające na wyznaczenie dziewięciu połączeń, w którym linie by się nie przecinały. Treść zagadki sprowadza się do utworzenia pełnego dwudzielnego grafu . Dowód nierozwiązywalności zagadki sprowadza się do wykazania, że nie jest planarny. Ów graf wraz z są elementarnymi grafami nieplanarnymi. W 1930 Kazimierz Kuratowski opublikował twierdzenie, w którym stwierdził, że graf jest planarny jeśli nie zawiera w sobie lub .
Inne powierzchnie Możliwość rozrysowania grafu bez przecięć zależy od rozmaitości topologicznej, na której jest on umieszczany. Takim przykładem jest torus, na którym graf można narysować bez przecinających się linii. thumb|center|250px|Rozwiązanie zagadki na torusie
Przypisy
Bibliografia
Linki zewnętrzne
Kategoria:Topologiczna teoria grafów Kategoria:Rozrywka matematyczna Kategoria:Zagadki