Problemet med tre huse og tre brønde er et klassisk matematisk puslespil : læg ikke-krydsende stier fra hver af de tre brønde til hvert af de tre huse . Formuleringen af problemet tilskrives Euler . I moderne litteratur findes det nogle gange i følgende form: er det muligt at lægge rør (muffer) fra tre kilder - elforsyning, gasforsyning og vandforsyning (" vand, gas, elektricitet ") til hvert af de tre huse uden krydsning på flyet .
Puslespillet har ingen løsning: topologisk grafteori, som studerer indlejring af grafer i overflader , giver et negativt svar på spørgsmålet om muligheden for at afbilde den tilsvarende graf på et plan uden at krydse kanter.
En komplet todelt graf, der repræsenterer problemet, kaldes " huse og brønde ", " brugsgraf " , Thomsen graf [ 1] .
Med hensyn til grafteori reducerer problemet sig til spørgsmålet om planheden af en komplet todelt graf . Denne graf svarer til en cirkulerende graf . Kazimir Kuratovsky i 1930 beviste, at han er ikke-plan, og derfor har problemet ingen løsning [2] .
Et af beviserne på umuligheden af at finde en flad indlejring bruger et casestudie, ved hjælp af Jordans sætning , overvejer forskellige muligheder for placeringen af toppunkter med hensyn til cyklusser af længde 4, og viser, at de er uforenelige med planaritetskravet [3] . Det kan også vises, at for enhver todelt plan graf uden broer med toppunkter og kanter , hvis vi kombinerer Eulers formel (her antallet af flader på en plan graf) med den observation, at antallet af flader ikke overstiger halvdelen af antallet af flader. kanter (da ethvert ansigt har mindst fire kanter, og hver kant tilhører præcis to flader). Desuden i grafen : og , som overtræder uligheden, så denne graf kan ikke være plan.
Problemets uløselighed følger direkte af hver af følgende vigtige sætninger om plane grafer: Kuratowskis sætning , ifølge hvilken plane grafer er præcis de grafer, der ikke indeholder subgrafer, der er homøomorfe i forhold til hele grafen , og Wagners sætning om, at plane grafer er i præcision , de grafer, der ikke indeholder enten , eller som underordnede , indeholder dette resultat.