>br>>>p>Um caminho Hamiltoniano, também chamado caminho Hamilton, é um caminho gráfico entre dois vértices de um gráfico que visita cada vértice exactamente uma vez. Se existir um caminho Hamiltoniano cujos pontos finais sejam adjacentes, então o ciclo gráfico resultante é chamado um ciclo Hamiltoniano (ou ciclo Hamiltoniano).
Um gráfico que possui um caminho Hamiltoniano é chamado um traçado.
Em geral, o problema de encontrar um caminho Hamiltoniano é NP-complete (Garey and Johnson 1983, pp. 199-200), pelo que a única forma conhecida de determinar se um dado gráfico geral tem um caminho Hamiltoniano é empreender uma pesquisa exaustiva
Um gráfico bipartido com um desequilíbrio de paridade de vértices 
não tem caminhos Hamiltonianos.
De encontrar um único caminho Hamiltoniano de um gráfico 
é implementado na Linguagem Wolfram como FindHamiltonianPath. Todos os caminhos hamiltonianos de um dado gráfico podem ser encontrados (ineficientemente) usando o comando HamiltonianPath no pacote Combinatorica da Wolfram Language` . Uma lista pré-determinada de todos os caminhos Hamiltonianos de muitos gráficos nomeados pode ser obtida usando GraphData, onde e ambas as orientações de caminhos estão incluídas (de modo que 
é considerado distinto de 
). Uma contagem pré-determinada do número correspondente de caminhos Hamiltonianos é dada por GraphData.
Os números totais de caminhos Hamiltonianos dirigidos para todos os gráficos simples de ordens 
, 2, … são 0, 2, 8, 50, 416, 5616, 117308, 4862736, … (OEIS A193352).
Rubin (1974) descreve um procedimento de pesquisa eficiente que pode encontrar alguns ou todos os caminhos e circuitos Hamilton num gráfico usando deduções que reduzem grandemente o retrocesso e o trabalho de adivinhação. Um algoritmo probabilístico devido a Angluin e Valiant (1979), descrito por Wilf (1994), também pode ser útil para encontrar ciclos e percursos Hamiltonianos. Um caminho Hamiltoniano entre dois vértices 
e 
pode ser encontrado se um algoritmo para ciclos Hamiltonianos estiver disponível. Isto pode ser feito verificando se o gráfico original 
contém a borda 
e adicionando-o se não for para obter 
. Uma vez que um caminho Hamiltoniano com pontos finais adjacentes é um ciclo Hamiltoniano e uma vez que 
e 
são agora adjacentes, encontrar um ciclo hamiltoniano e dividir-se na margem dá um caminho hamiltoniano de 
a 
em 
. Da mesma forma, se não existir nenhum ciclo Hamiltoniano em 
, então não existe nenhum caminho Hamiltoniano de 
a 
em 
.
A tabela seguinte resume os números dos caminhos (não direccionados) Hamiltonianos em várias classes de gráficos.
| graph | formula |
| barbell graph |  |
gráfico de coquetel de festa  |
|
gráfico completo  |
 |
gráfico bipartido completo  |
|
 |
|
gráfico do ciclo  |
|
 |
|
ladder graph  |
|
Escada Möbius  |
|
gráfico do caminho  |
1 |
gráfico de prisma  |
 |
| gráfico de sol |  |
gráfico de roda  |
 |
-crossed prism graph
n 
Relações de recorrência para o número de caminhos Hamiltonianos dirigidos para algumas famílias gráficas são resumidas abaixo.
| graph | order | recurrence |
| gráfico antiprisma | 9 |  a_n=a_(n-9)+a_(n-8)-3a_(n-7)-5a_(n-6)+5a_(n-5)+7a_(n-4)-4a_(n-3)-6a_(n-2)+5a_(n-1) |
| crown graph | 3 |  |
gráfico de prisma  |
6 |  |