Teoremas de Dirac y Ore.
Un camino hamiltoniano en una gráfica $G$ es un camino que visita cada vértice exactamente una vez. Si el camino empieza y termina en vértices adyacentes, permitiendo que el camino se cierre en un ciclo, lo puedes llamar ciclo hamiltoniano. A diferencia de los caminos eulerianos (que visitan cada arista exactamente una vez) donde las condiciones necesarias y suficientes son simples y tienen que ver con la paridad de los grados, determinar si una gráfica cualquiera contiene un ciclo hamiltoniano es un problema NP-completo. No se conoce una caracterización simple (como "todos los grados son pares") que funcione para todas las gráficas.
Sin embargo, en el mundo de las olimpiadas de matemáticas, lo normal es apoyarse en condiciones suficientes. Estos son teoremas que dicen que si una gráfica tiene "suficientes" aristas o grados de vértices lo bastante altos, se garantiza que sea hamiltoniana. La intuición es que si cada vértice está conectado a muchos otros, la gráfica es lo suficientemente "densa" para dejarte mover de cualquier punto a cualquier otro sin que te quedes atrapado o te saltes vértices.
Los dos resultados más fundamentales en esta área son el Teorema de Dirac y el Teorema de Ore. El Teorema de Dirac da una condición basada en el grado mínimo de la gráfica, mientras que el Teorema de Ore generaliza esto fijándose en la suma de los grados de los vértices que no son adyacentes