Van-e valamilyen összefüggés mellyel meglehet állapítani, hogy egy adott ábra/gráf megrajzolható-e egy vonallal a ceruza felemelése nélkül?

Meglepődnék, ha nem szerepelne ez a kérdés itt már legalább egy tucatszor, de 0. közelítésben a válasz:

[link]

Megpróbálom elmagyarázni általános szinten.

Ha a ceruza áthalad egy ponton (csúcson), akkor lesz egy vonal (él), amin keresztül a ceruza „beérkezik” az adott pontba (csúcsba), és lesz egy olyan vonal (él), amin „távozik” a pontból (csúcsból). Ergo minden köztes pontba páros számú vonalnak kell befutnia. Két pont lehet kivétel, a kezdőpont, ahova a ceruzát leteszed – hiszen innen úgy indul egy egy vonal, hogy nem kellett beérkeznie máshonnan –, és a végpont, ahol a ceruzát felemeled. Ennél a két végpontnál lehet a találkozó vonalak száma páratlan.

Ilyen szempontból három eset van:

1. Minden csúcsban páros vonal találkozik. Ekkor bármelyik pontból elindulva meg lehet rajzolni az alakzatot, és a végpont ugyanaz lesz, mint a kezdőpont.

2. Pontosak két olyan pont van, amiben páratlan vonal találkozik. Ekkor az egyik ilyennek kell lennie a kezdő-, a másiknak a végpontnak.

3. Minden más esetben az ábra (gráf) nem rajzolható meg egy vonallal.

Az első pont csak akkor igaz, hogyha a gráf összefüggő, vagy legfeljebb izolált csúcsokat tartalmaz; például ha lerajzolok két külön négyzetet, ott is minden csúcsba 2-2 él fut be, mégsem tudom lerajzolni őket anélkül, hogy a ceruzát felemelném.

Egyébként ez egy nem triviális következmény (vagyis ha összefüggő a gráf, és minden csúcsba páros sok él fut), de a bizonyításra, gondolom, nincs szükséged, így elég, ha annyit tudsz, hogy igaz.