Caminos que pasan por cada vértice exactamente una vez.
Un camino hamiltoniano en una gráfica simple es un camino que visita cada vértice exactamente una sola vez. Si el camino empieza y termina en vértices adyacentes, permitiendo que el camino se cierre en un ciclo, lo llamamos ciclo hamiltoniano. A una gráfica que contiene un ciclo hamiltoniano le decimos gráfica hamiltoniana. Este concepto es diferente al de los caminos eulerianos, que visitan cada arista exactamente una vez. Recuerda que una gráfica conexa tiene un circuito euleriano si y solo si cada vértice tiene un grado par; sin embargo, no conocemos ninguna condición simple necesaria y suficiente para determinar si una gráfica es hamiltoniana. Por eso, determinar si una gráfica general es hamiltoniana es un problema NP-completo.
En las olimpiadas de matemáticas como el AIME o la USAMO, vas a ver que los problemas de caminos hamiltonianos suelen enfocarse en condiciones suficientes (densidad de aristas) o en probar que una estructura específica de gráfica permite o no tener tal camino. Tu intuición debe depender de la "densidad" de la gráfica: si notas que una gráfica tiene suficientes aristas comparadas con su número de vértices, o si el grado mínimo de los vértices es lo suficientemente alto, la gráfica se ve "forzada" a ser hamiltoniana. Por el contrario, si la gráfica tiene "cuellos de botella" o conjuntos de corte que la fragmentan en demasiadas componentes al quitarlos, no puede existir un ciclo hamiltoniano.
Las ideas clave en esta área involucran la teoría de gráficas extremales.