Postupnosť nadväzujúcich vrcholov a hrán (začínajúcu aj končiacu vrcholom) nazývame sled. Formálne je to konečná postupnosť
$v_0,e_1,v_1,e_2,v_2,\dots,e_k,v_k$,
kde $v_0,v_1,\dots,v_k$ sú vrcholy a $e_1,e_2,\dots,e_k$ sú hrany, pričom platí, že hrana $e_1$ spája vrcholy $v_0$ a $v_1$, hrana $e_2$ spája vrcholy $v_1$ a $v_2$ atď... Neformálne sa dá na sled pozerať ako na nejakú prechádzku po grafe, kde začíname aj končíme v nejakom vrchole a medzi vrcholmi sa pohybujeme po hranách (v angličtine sa sled aj nazýva walk). Ak hovoríme o sledoch v orientovaných grafoch, vyžadujeme, aby všetky hrany boli orientované v smere našej prechádzky (teda $e_1$ je hrana z $v_0$ do $v_1$, $e_2$ je hrana z $v_1$ do $v_2$ atď.). Dĺžku sledu definujeme ako počet hrán v ňom (ak sa nejaká hrana opakuje, rátame každý jej výskyt), prípadne pri ohodnotených grafoch ako súčet dĺžok hrán.
Sled, v ktorom sa neopakujú hrany, nazývame ťah. V príklade s kreslením jedným ťahom sa vlastne snažíme v grafe nájsť ťah, ktorý prechádza všetkými hranami.
Sled, v ktorom sa neopakujú vrcholy, nazývame cesta. Každá cesta je súčasne aj ťah -- ak by sme po nejakej hrane prešli dvakrát, museli by sme aj niektorý vrchol navštíviť dvakrát.
Ťah, ktorý sa začína aj končí v tom istom vrchole, ale okrem toho sa v ňom žiadne dva vrcholy neopakujú, nazývame cyklus, alebo kružnica. Graf, ktorý neobsahuje kružnice, voláme acyklický.
Vzdialenosť dvoch vrcholov je dĺžka najkratšej cesty medzi nimi.