Definição

Um caminho é um grafo não-vazio $P = (V,A)$ da forma

$V = \{x_{0}, x_{1}, …, x_{k}\}$ e $A = \{x_{0}x_{1}, x_{1}x_{2}, …, x_{k-1}x_{k}\}$, com todos os $x_i$ distintos.

Os vértices $x_0$ e $x_k$ são ligados por $P$ e são chamados extremidades, enquanto os demais vértices são interiores.

O tamanho de um caminho é o mesmo de seu conjunto de arestas.