Három ház–három kút-probléma

a gráf

nem oldható meg

A három ház–három kút-probléma (vagy víz–gáz–villany-probléma, három közmű problémája) a gráfelméleti Kuratowski-tételben szereplő egyik gráfhoz – a három ház–három kút-gráfhoz – kapcsolódó probléma. A probléma így fogalmazható meg: Tervezhető-e három házhoz és három kúthoz olyan síkbeli úthálózat, hogy minden háztól minden kútig vezessen egy-egy út és ezek az utak ne keresztezzék egymást? A válasz: Nem lehet. A három ház–három kút-gráf egy teljes páros gráf, jelölése K_3,3. Ez a gráf – az öt csúcspontú teljes gráf (K₅) mellett – meghatározó jelentőségű a gráfok síkbarajzolhatóságának problémakörében.

Források

• három ház–három kút-probléma, Matematikai kislexikon, Budapest, Műszaki Könyvkiadó, 1972