Para probar esto se muestra en (1) que toda solución factible contiene solamente una secuencia cerrada de ciudades, y en (2) que para cada uno de los recorridos que cubren todas las ciudades, hay valores para todas las variables formula_2 que satisfacen las restricciones.