L a séta hossza. L=0 lehetséges, azaz fenti definíciónkba ``belefér'' a v0 sorozat.
Lemma: Ha az x és y csúcsok között van S séta, akkor van olyan is, amely pontsorozatában nincs ismétlődés. Ez a pontismétlődés nélküli xy séta olyannak is választható, hogy élei S élei közül kerüljenek ki.
Bizonyítás: Ha az S séta pontjai között ismétlődés van, akkor egy csúcs első és második látogatása közötti rész kivágahtó S-ből és így rövidebb xy sétához jutunk. Ez a kivágás a séta élhalmazát nem növelheti. Ezt a kivágás operációt addig ismételjük amíg lehetséges. Elakadáskor (ennek be kell következni, mert sétánk hossza szigorúan csökken) egy olyan xy sétához jutunk, ami nem tartalmazhat csúcsismétlődést, azaz út.
Sétálás egy gráfban: S0=v0 (0 hosszú séta), S1,S2,S3,... séta-sorozat, ahol Si egy i hosszú séta, a Si-1 séta folytatása (egy éllel (egy új lépés) és egy csúccsal (új utolsó csúcs)).
Tehát sétálás egy folyamat, amely időben zajlik: egy bejárás növekedése, ahogy az idő telik. A sétálásra úgy is gondolhatunk, mint egy film kockáinak sorozatára, ahol minden filmkockát egy lépéssel későbbi állapotot rögzítő filmkocka követ.
Ha egy nem izolált pontból indul a sétánk, akkor tetszőleges hosszú sétát tehetünk. Utolsó lépésünkön visszalépni mindig egy lehetőség a séta folytatására. Azaz van végtelen séta egy nem üres élhalmazzal rendelkező gráfban.
Ha az élek nem ismétlődnek, akkor vonalról beszélünk.
Vonal hosszát mint séta hosszát értelmezzük. A 0, illetve 1 hosszú séta biztosan vonal is.
Mohó vonalnövelés egy gráfban: V0=v0 (0 hosszú vonal), V1,V2,V3,... vonal-sorozat, ahol Vi egy i hosszú vonal, a Vi-1 vonal folytatása (egy éllel (egy új lépés) és egy csúccsal (új utolsó csúcs)).
Egy vonalnövelés mindig elakad. Egy vonal hosszára a gráf éleinek száma határt szab.
Könnyen definiálható egy nem szükségszerűen 0 hosszú vonalból induló mohó vonalnövelés is.
Lemma: Egy páratlan fokszámú pontból induló mohó vonalnövelés egy a kiinduló ponttól különböző páratlan fokú pontban akad el.
Következmény: Ha egy gráfban van páratlan fokú pont, akkor van másik is.
Következmény: Egy gráfban a páratlan fokú pontok száma páros.
Ha a csúcsok nem ismétlődnek (ekkor az élek között sem lehet ismétlődés), akkor útról beszélünk.
Út hosszát mint séta hosszát értelmezzük. A 0 hosszú séta biztosan út is. A 1 hosszú séta akkor és csak akkor út ha a benne szereplő él nem hurokél.
Mohó útnövelés egy gráfban: U0=v0 (0 hosszú út), U1,U2,U3,... út-sorozat, ahol Ui egy i hosszú út, a Ui-1 út folytatása (egy éllel (egy új lépés) és egy csúccsal (új utolsó csúcs)).
Egy útnövelés mindig elakad. Egy út hosszára a gráf csúcsainak száma (|V|-1) határt szab.
Lemma: Egy d minimális fokú egyszerű gráfban a mohó útnövelés legalább d hosszú úthoz vezet
A fenti fogalmak zárt változatait is bevezetjük.
Egy séta zárt séta vagy körséta, ha kezdőpontja és végpontja megegyezik.
Hasonlóan beszélhetünk zárt vonalról (illetve alternatív szóhasználattal körvonalról).
Út esetén nem tehetjük fel (a 0 hosszú út kivételével), hogy a kezdő és a végpont megegyezik. Egy rokon fogalmat azért bevezetünk. A v0,e1,v1, e2,v2,...,vL-1, eL,vL séta kör, ha
Az élek különbözőségének csak az L=2 esetén van szerepe. L>2 esetén az élek különbözősége a csúcsokra tett feltételből következik.
A kör hosszát mint séta hosszát értelmezzük. Egy L hosszú kör élhalmaza és ponthalmaza is L elemű, élsorozata L hosszú, pontsorozata L+1 hosszú. 1 hosszú kör élhalmaza egy hurokél, 2 hosszú kör élhalmazát két különböző párhuzamos él alkotja.