Dois ou mais caminhos são independentes se nenhum deles contém um vértice interno do outro.
Dois $a-b$ caminhos, por exemplo, são independentes se, e somente se, $a$ e $b$ são seus únicos vértices em comum.