Suponha que a área de venda de um caixeiro viajante inclua várias cidades, muitas das quais, aos pares, estão conectadas por rodovias. O trabalho do caixeiro requer que ele visite cada cidade pessoalmente. Sob que condições seria possível estabelecer uma viagem circular (que o leve ao ponto de partida) de forma a que ele visite cada cidade exatamente uma vez?