Formulemos primero la idea de Pavel en términos de el teorema de Bondy-Chvátal en lugar del Teorema de Ore.
El teorema afirma que un grafo es hamiltoniano si y sólo si su cierre es hamiltoniano, donde el cierre se define como el único grafo resultante de añadir sucesivamente aristas entre cualquier par $u,v$ de vértices con $d(u)+d(v)\ge n$ .
Por tanto, un grafo no hamiltoniano con el máximo número de aristas debe tener $d(u)+d(v)\lt n$ para todas las aristas que faltan, ya que de lo contrario su cierre sería un gráfico no hamiltoniano diferente con más aristas. Así, dos vértices $u,v$ no conectados por una arista sólo tienen $d(u)+d(v)\lt n$ en lugar del máximo posible $2n-3$ bordes incidentes, por lo que al menos $2n-3-(n-1)=n-2$ los bordes faltan. Por lo tanto, el gráfico tiene como máximo $\binom n2-(n-2)=\binom{n-1}2+1$ bordes.
Pasando ahora a su problema de encontrar el número máximo de aristas de un grafo no hamiltoniano en $n$ vértices de grado mínimo $2$ busquemos dos aristas perdidas sin vértices en común. Un momento de reflexión muestra que si todos los pares de aristas que faltan tienen al menos un vértice en común, eso significa que o bien hay un solo triángulo de aristas que faltan, en cuyo caso el grafo es hamiltoniano, o bien todas las aristas que faltan tienen el mismo vértice en común, en cuyo caso el grafo también es hamiltoniano ya que el vértice común tiene al menos dos aristas que lo conectan con el resto del grafo completo.
Por lo tanto, dado que el grafo no es hamiltoniano, existe un par de vértices disjuntos de aristas perdidas. Los cuatro vértices implicados podrían tener un máximo de $4(n-1)-\binom42=4n-10$ aristas incidentes, pero por el teorema de Bondy-Chvátal tienen, de hecho, como máximo $2(n-1)=2n-2$ bordes incidentes, por lo que al menos $2n-8$ los bordes faltan. Eso nos lleva casi hasta el final, ya que $\binom n2-(2n-8)=\binom{n-2}2+5$ .
Estrechando la brecha desde el otro lado, encontramos que en realidad podemos mejorar su construcción en una arista conectando los dos vértices solitarios no entre sí, sino por separado a los mismos dos vértices de $K_{n-2}$ . Ambos siguen desaparecidos $n-3$ aristas, pero ahora una de ellas se cuenta doble, por lo que este gráfico tiene $\binom{n-2}2+4$ bordes y no es hamiltoniano para $n\gt4$ .
Ahora sólo queda tratar el caso de $\binom{n-2}2+5$ bordes, correspondientes a $2n-8$ bordes perdidos. Como las aristas entre los cuatro vértices se cuentan doblemente en la aplicación del teorema, no puede haber tales aristas. Por tanto, podemos aplicar el teorema a los seis pares de los cuatro vértices. Si se aplica al par con los dos grados más bajos, se observa que todos deben tener exactamente el grado $(n-1)/2$ . Para obtener una cantidad suficiente de $n$ , eso significa que están conectadas al resto de $K_{n-4}$ por suficientes aristas para permitir un ciclo hamiltoniano. Es posible que haya que hacer un trabajo de casos un poco tedioso para excluir los casos especiales para pequeñas $n$ .
En resumen, para un tamaño suficientemente grande $n$ ( $n\gt16$ ), el número máximo de aristas en un grafo no hamiltoniano con grado mínimo $2$ es $\binom{n-2}2+4$ y este límite es alcanzable mediante una construcción explícita.
P.D.: De hecho, existe un caso especial con $n=7$ : Conecta cada uno de los cuatro vértices solitarios con todos los vértices de $K_3$ . Eso hace un total de $15=\binom{7-2}2+5$ aristas; el grado mínimo es $3$ y el gráfico no es hamiltoniano, ya que los tres vértices de $K_3$ puede utilizarse para alcanzar como máximo tres de los cuatro vértices solitarios. Esto deja abierta la cuestión de si el máximo para $n=9,11,13,15$ es $\binom{n-2}2+4$ o $\binom{n-2}2+5$ .
P.P.S.: Una construcción análoga da lugar a otro caso especial con $n=9$ : Conecta cada uno de los cuatro vértices solitarios con los mismos cuatro vértices de $K_5$ . Los bordes cruzados aún no son suficientes para permitir un ciclo hamiltoniano. Sospecho que esta es la última excepción, ya que una construcción análoga para $n=11$ (conectando los cuatro vértices solitarios a los mismos cinco vértices de $K_7$ ) falla y permite un ciclo hamiltoniano.
