[Enunciado] Seja G um grafo com custos nos arcos mas sem ciclos negativos. Seja P um caminho de custo mínimo em G. Queremos mostrar que P é essencialmente simples. Mais precisamente, queremos mostrar que alguma subsequência de P é um caminho simples com a mesma origem de P, o mesmo término de P e o mesmo custo de P.
Seja v0-v1-…-vk a sequência de vértices de P. Suponha que P não é simples. Seja j o menor índice tal que vj ≡ vi para algum i < j. Seja C o ciclo vi-vi+1-…-vj−1-vj e Q o caminho v0-v1-…-vi-vj+1-…-vk. Por hipótese, C tem custo positivo e P é mínimo. Logo, o custo de Q é igual ao de P e o custo de C é nulo.
Se Q for simples, não há mais o que fazer. Senão, repita a construção com Q no lugar de P. Como o comprimento de Q é menor que o de P, esse processo termina depois de um número finito de passos e produz um caminho simples com as propriedades desejadas.