[Estudiantee]

¿Alguien tiene o sabe donde puedo encontrar la demostración de la siguiente proposición?
 Si G es un grafo simple con \( |V|=n\geq{3} \), G posee un ciclo hamiltoniano, si es \( |E|\geq{\displaystyle\binom{n-1}{2}+2} \)
Siendo E el número de aristas, V el número de vértices y n el número de vértices de G.
Gracias

[Weip]

Aquí tienes la demostración, es el corolario 11.6: https://books.google.es/books?id=lHqqjoR0b1YC&pg=PA580&lpg=PA580&dq=si+g+grafo+simple+con+ciclo+hamiltoniano&source=bl&ots=gSnYivRi_k&sig=xCmShXE0S5CVo977l-ZjrCkFxUQ&hl=es&sa=X&ei=in1wVd-fEIrpUqaYgNAO&ved=0CFUQ6AEwCQ#v=onepage&q=si%20g%20grafo%20simple%20con%20ciclo%20hamiltoniano&f=false

[Estudiantee]

Pero para el grafo 4-regular, es decir un cuadrado, para ese no se cumple la condición y sin embargo es hamiltoniano

[Luis Fuentes]

Hola

Pero para el grafo 4-regular, es decir un cuadrado, para ese no se cumple la condición y sin embargo es hamiltoniano

El teorema da una condición suficiente pero no necesaria.

Saludos.

P.D. En el Spoiler está el Teorema y su Corolario:

Spoiler

[cerrar]

[Estudiantee]

y cual sería la condición necesaria?

[Luis Fuentes]

Hola

y cual sería la condición necesaria?

Hablas de "la" necesaria como si hubiese una sola.

Lo que no hay es una condición necesaria y suficiente (cómoda) que equivalga a la existencia de un ciclo Hamiltoniano.

Hay varias teoremas que dan condiciones suficientes y otros que dan condiciones necesarias.

Un ejemplo de condición necesaria es esta:

http://en.wikipedia.org/wiki/Grinberg%27s_theorem

Si buscas en google por "necessary condition hamiltonian cycle" puedes encontrar más.

Saludos.

[Estudiantee]

Puedo utilizar la condicion\( E\leq{\displaystyle\binom{n-1}{2}+2} \) para decir un grafo con numero de aristas 23 y numero de vertices 15 para justificar que no es hamiltoniano?

[Weip]

No, no puedes. La negación del enunciado te serviría si ya supieses de antemano que el grafo no es hamiltoniano y quisieras una acotación de \( |E| \).

[Estudiantee]

Puedo usar el teorema de dirac para justificarlo?

[Weip]

Con el teorema de Dirac sí. Ningún problema. Pero asegúrate de que tu grafo cumple las hipótesis del teorema. Es decir, que el número de vértices sea mayor que tres y que cada vértice tenga grado mayor o igual a \( n/2 \) siendo \( n \) el número de vértices.