Hogyan mutassam meg, hogy tetszőleges páratlan hosszúságú zárt séta tartalmaz kört. Igaz-e ez páros hosszúságúra?

Séta esetén a gráfot úgy járjuk be, hogy egy csúcsról akkor lépünk egy másik csúcsra, ha azok össze vannak kötve éllel, ugyanarra a csúcsra többször is léphetünk, és ugyanazt az élt többször is használhatjuk. Zárt séta esetén vissza kell jutnunk a kezdőpontra. Egy zárt séta akkor kör, ha legalább annyi különböző élt használtunk, mint ahány csúcsot bejártunk. N hosszú séta esetén N (nem feltétlenül különböző) élen megyünk át.

Ezzel már láthatjuk, hogy ha N-hosszú utunk van, akkor 2N hosszú sétát kapunk, ebben viszont nincs kör.

Bizonyításban sose voltam jó, de biztos, hogy könnyű bizonyítás van rá.

Kérdéses, hogy mit értesz az alatt, hogy "tartalmaz" kört? Mert ha azt, hogy egy sétának van egymásutáni része (élsorozata), ami kör, akkor ez nem igaz. Egy 5 csúcsú gráf esetén (A,B,C,D,E):

A->B->A->B->C->D->E->A

Ha azt, hogy a sétával bejárt részgráf (élek és csúcsok, amiket a séta érint) tartalmaz kört, akkor következőképp:

Ha páratlan hosszú, akkor az azt jelenti, hogy van olyan él, amit páratlanszor jártunk be.

Legyen ez az él (a,b). Ha a vagy b (most legyen a) a kezdőpont, akkor biztos, hogy van egy út a és b közt, hisz különben nem tudtunk volna páratlanszor végigmenni (a,b)-n és a-ban végezni.

Ha se a, se b nem kezdőpont akkor viszont kell lennie egy (a,b) éltől független út a és b közt, ami körbe zárul (a,b)-vel. Ha nem lenne, akkor nem lehetne zárt a séta, hiszen az (a,b) élt elvágva a séta olyan komponensekre esne szét, amik közt nincs él, és mivel (a,b)-n páratlanszor mentünk át, ezért a kezdőpontot nem tartalmazó komponensben végeztünk volna, azaz biztos nem a kezdőpontban.

Szerintem ez így korrekt, de kritikusan állj hozzá.