Ver con los ciclos de cada longitud

Question

Probar que en un gráfico en $n$ vértices con grado min más de $n \over 2$, hay ciclos de cada longitud entre 3 y $n$ incluido.

Sé que del teorema de Dirac, $G$ tiene un hamiltoniano del ciclo, es decir un ciclo de longitud $n$. Estoy tratando de mostrar que el ciclo tenga suficiente acordes para que hay ciclos de cada longitud, pero tengo problemas para hacer eso exactamente.

Answer 1

Deje $v$ ser un vértice de $G$. Deje $H=G-v$. A continuación, $\delta(H)\geq\frac{n-1}2$ y desde $H$ sólo ha $n-1$ elementos, $H$ es de Hamilton, lo que significa que $G$ $n-1$ciclo $C$.

Ahora $d(v)$ tiene más de $\frac n2$ vecinos, todos en $C$, de modo que al menos dos de ellos son adyacentes, lo que nos da un triángulo y un ciclo Hamiltoniano.

Deje $v_1,\ldots,v_{n-1}$ ser los vértices de $C$ y asumir que no hay ciclo de longitud $t$ algunos $3<t<n-1$.

Si edge $vv_i$ existe, entonces borde de $vv_{i+t-2}$ (índices de $\pmod{n-1}$) no existen, ya que se iba a producir $t$ciclo $vv_i\ldots v_{i+t-2}v$. Pero esto significa que $v$ puede tener grado en la mayoría de las $\frac{n-1}2$.

Esta contradicción demuestra la reclamación.