歩道・小道・道・閉路

頂点の列 $W=v_0v_1\cdots v_k$ で、各 $i$ について $v_{i-1}v_i\in E(G)$ であるものを $v_0$ から $v_k$ への歩道といい、$k$ をその長さという（多重グラフでは使う辺 $e_i$ も指定する）。辺を重複して使わない歩道を小道、頂点を重複して通らない歩道を道という。$v_0=v_k$ である歩道を閉じているという。長さ $k\ge3$ の閉じた歩道で、$v_0,\dots,v_{k-1}$ が相異なるものを長さ $k$ の閉路という（定義 2.1［グラフと行列式］ の閉路と同じもの）。道・閉路は、それが使う頂点と辺からなるグラフとも見なす。

道 $P=v_0\cdots v_k$ と $0\le i\le j\le k$ に対し、部分列 $v_i\cdots v_j$ を $v_iPv_j$ と書く。