Gráfelméletben ezt úgy hívják, hogy síkbarajzolható-e a gráf. Ha fel lehet a gráfot rajzolni egy síkban úgy, hogy az élek nem metszik egymást, azt síkbarajzolhatónak hívják.

Nem tudom, miket tanultatok már gráfelméletből. Ha még nem sokat, akkor nem lehet mást csinálni, mint rajzolgatni, és kiderül, hogy nincs megoldás. (Ez egyébként a nevezetes `K_(3,3)` gráf, ami nem síkbarajzolható.)

Ha tanultátok az Euler formulát, akkor be is lehet bizonyítani:

Az Euler formula szerint egy `v` csúcsból és `e` élből álló síkgráf esetén az élekkel határolt síktartományok `t` számára igaz ez az öszefüggés:
`v-e+t=2`

Na most a feladat elrendezése olyan, hogy az élek az egyik oldalról (házak) a másik oldalra (közművek) mennek, onnan pedig vissza. Tehát nincs vízszintesen menő él a házak között, se a közművek között. Ennek az a következménye, hogy páros darab él kell ahhoz, hogy visszaérjünk a kiindulási csúcshoz. 2 nem elég (mert két csúcs között nincs két él), ezért ez a páros szám legalább 4. Vagyis egy síkterületet (ami az élekből egy zárt kör) legalább 4 él határol. Ez minden területre igaz. Minden él két területet választ el, ezért `4t ≤ 2e`.

`2t ≤ e`
Ebbe beírva az Euiler formulát ezt kapjuk:
`2(2-v+e) ≤ e`
`e ≤ 2v-4`

A mi esetünkben `v=6`, `e=3·3`, erre nem teljesül ez az egyenlőtlenség, ezért nem síkbarajzolható a gráf.