Teoría de grafos Pregunta sobre una observación en los ciclos hamiltonianos Prueba

Question

Estoy repasando unos apuntes de Teoría de Grafos. Se demuestra el siguiente teorema:

Teorema 1: Dejemos que $G$ sea un gráfico de orden $n$ ( $ n \geq 3$ ) tal que $ \delta(G) \geq \frac{n}{2} $ . Entonces $G$ es hamiltoniano.

Estoy contento con el enunciado y la demostración de este teorema. A continuación, las notas demuestran el siguiente teorema:

Teorema 2: Dejemos que $G$ sea un gráfico de orden $n$ ( $n \geq 3$ ) tal que $G$ está conectado y $ \delta(G) \geq \frac{k}{2} $ , donde $ k < n $ . Entonces $G$ tiene un camino de longitud k.

Estoy contento con la prueba de esto. A continuación, las notas hacen la siguiente observación

Observación: Necesitamos $k < n $ Por ejemplo $ G = K_k $ y necesitamos $G$ para estar conectados, por ejemplo, dos copias disjuntas de $K_k$ .

No entiendo este comentario. Claramente $k$ no puede ser mayor que $n$ (ya que obviamente no puede haber un camino a través de más de $n$ vértices en un gráfico con $n$ vértices). Así que la observación debe significar que no podemos tener $k = n $ . Pero si $k = n$ ¿entonces no es lo mismo que el Teorema 1? Tampoco veo la relación del ejemplo; si $ G = K_n $ ¿Entonces el teorema sigue funcionando?

Gracias por su ayuda.

Answer 1

Diferentes autores definen camino de manera diferente, pero parece que el autor de sus notas utiliza definiciones similares a las utilizadas en la obra de West Introducción a la teoría de grafos . Para él un camino es "un grafo simple cuyos vértices pueden ordenarse de manera que dos vértices son adyacentes si y sólo si son consecutivos en la lista", y un ciclo es "un grafo con igual número de vértices y aristas cuyos vértices pueden colocarse alrededor de un círculo de manera que dos vértices son adyacentes si y sólo si aparecen consecutivamente a lo largo del círculo". Según estas definiciones, un camino nunca puede ser un ciclo: en cualquier listado de los vértices de un ciclo en el que los vértices consecutivos de la lista sean adyacentes en el grafo, el primer y el último vértice de la lista son también adyacentes en el gráfico. Esta definición de camino también implica que ningún camino en un grafo puede tener más vértices que el propio grafo. En particular, $K_n$ no contiene ninguna ruta con $n+1$ vértices y, por tanto, ningún camino de longitud $n$ .