Número máximo de aristas en un grafo hamiltoniano no

Question

Necesito mostrar que el máximo número de aristas de la no-Hamiltonianos, simple gráfico, en $n$ vértices señaló $t(n,H_n)$$\binom{n-1}{2} + 1$. Es esencial para mostrar los límites inferiores y superiores para esta pregunta.

Ahora, puedo ver por qué tengo que mostrar el límite superior - para $t(n,H_n) > \binom{n-1}{2} + 1$ hay una camarilla en $n-1$ vértices y uno de los otros vértices con al menos 2 de los bordes. Sin duda, un ciclo Hamiltoniano existir en dicho gráfico.

¿Y el límite inferior, aunque? Am tengo que demostrar que para cada $t(n,H_n) \leq \binom{n-1}{2} + 1$ no hay ningún ciclo Hamiltoniano? Por la negación, me parece no avanzar en cualquier lugar, porque no sé de ninguna de las condiciones necesarias para un ciclo Hamiltoniano de existir, junto a la corte de vértice. Alguien puede darme una pista sobre que?

Gracias de antemano.

Answer 1

Encontrado prueba mucho más fácil para la parte más difícil, aplicando el teorema del mineral: si $G$ es completa, existe un ciclo hamiltoniano. Así que supongo que no es. Nosotros tomar algunos vértices no vecino $v,w$ y borrar de la gráfica. El resultado gráfico $G'$ - $|E(G')| \geq \binom {n-1}{2} + 2 - (d(v)+d(w))$. En el gráfico completo en $n-2$ vértices hay son bordes de $\binom {n-2}{2}$. Así, por último, tenemos que $$\binom{n-2}{2} \geq \binom{n-1}{2} + 2 - (d(v)+d(w))$$ and after some easy operations, we get that $%$ $d(v)+d(w) \geq n$que es exactamente de mineral para un grafo hamiltoniano existir.

Answer 2

Una diferente de la inducción de la solución:

Inducción de la hipótesis: Un (simple) grafo G con $\binom {n-1} 2 +2$ bordes tiene un ciclo hamiltoniano.

Para$n=2$$n=3$, podemos demostrar que el reclamo por agotar todas las posibilidades(donde $n$ es el número de vértices).

Para $n>3$: Hay un vértice con grado de al menos $n-2$. Esto es cierto porque hay $\dfrac{(n-1)(n-2)}2+2$ bordes, por lo tanto la suma de los grados de todos los vértices es $(n-1)(n-2)+4=n^2-3n+2$. Supongamos, todos los vértices tenido grado $n-3$ o menos, entonces se podría hacer hasta un máximo de $n(n-3)$.

Caso $1$: Hay un vértice de grado $n-1$

La eliminación de este vértice crea un $n-1$ vértice de la gráfica con $\dfrac{(n^2-5n+8)} 2$ bordes, mientras que necesitamos $\dfrac {(n-2)(n-3)}2+2=\dfrac{(n^2-5n+10)}2$ para un ciclo hamiltoniano. Pero es suficiente para un hamiltoniano ruta de existir (de inducción). Desde entonces, la quita vértice tiene grado $n-1$, el hamiltoniano ruta de acceso en el menor gráfico se puede convertir en un ciclo hamiltoniano en el más gráfico.

Caso $2$: Hay un vértice con $n-2$ y sin vértices con grado de $n-1$.

La eliminación de este vértice se crea un gráfico con $\dfrac{(n^2-3n+2)}2-(n-2)+2=\dfrac{(n-2)(n-3)}2 +2$. Por inducción, el más pequeño grafo contiene un ciclo hamiltoniano. Desde entonces, la quita vértice tiene grado $n-2$, podemos encontrar dos vértices adyacentes en el ciclo hamiltoniano e inserte el vértice allí.(es por eso que se requiere de la inducción de la base de caso por $n=3$) $\blacksquare$

Ejemplo de una (¿la única?) el gráfico de $\binom {n-1} 2+1$ bordes y no hamiltonianos: Unión de $K_{n-1}$ y un vértice fuera que comparte una arista con exactamente un vértice de $K_{n-1}$ .

Answer 3

Esto es esencialmente Corolario 4.6 en el libro "la Teoría de grafos con aplicaciones" de J. A. Bondy y U. S. R. Murty, que está disponible aquí. Me pregunto si hay una sencilla prueba de esta afirmación. Tal vez hay una, pero no sé. Ya se dijo que esta es una tarea problema, creo que puede ser capaz de aplicar algún teorema que ha aprendido en su clase. Si usted ha aprendido Chvatal del teorema en su clase (ver Teorema 4.6 del libro mencionado) que dice que:

Si $G$ es un no-Hamiltonianos simple gráfico con $n\geq 3$ vértices, entonces $G$ es de grado-majorised por algunos $C_{m,n}:=K_m\vee(K_m^c+K_{n-2m})$

entonces usted puede obtener el resultado requerido fácilmente de la siguiente manera, como se muestra en el libro: $$|E(G)|\leq |E(C_{m,n})|=\frac{1}{2}\Big[m^2+(n-2m)(n-m-1)+m(n-1)\Big]\leq{n-1\choose 2}+1.$$ Por otro lado, se puede caracterizar $G$, cuando la igualdad se mantiene.