¿Cómo probar que existe un ciclo?

Question

Dado un grafo $G = (V, E)$, donde el grado de cada vértice es al menos $d$ y $d > 2$, debe haber un ciclo de longitud al menos $d + 1$ en $G.

Dado que $d\geq2$ eso demuestra que el número de aristas es mayor que el número de nodos, lo que significa que seguramente existe un grafo.

pero ¿cómo probar que existe un ciclo de longitud al menos d+1?

alguna pista

Answer 1

Considera el camino más largo $P$ en $G$. Sea $v$ un extremo del camino. Se sigue que todos los vecinos de $v$ deben estar en $P$, de lo contrario podríamos extender $P$ contradiciendo su maximalidad. Existen al menos $d$ vecinos de $v$ en $P. Sea $u$ el vecino de $v$ más alejado de $u$ en $P. Entonces $vPuv$ es un ciclo de longitud al menos $d+1$.

Por cierto, no puedes concluir que $|E| > |V|$ a partir de la suposición de $d\ge 2$ (tampoco es una suposición necesaria). Considera cualquier ciclo, por ejemplo.

Edit: No estamos diciendo que nuestro camino $P$ sea un ciclo, sino que contiene un ciclo. Para ser concretos, digamos que $$P=(v_0,\ v_1,\ v_2,\ \cdots,\ v_k)$$ Entonces sabemos que $k\ge d$ y que $v_0$ tiene a todos sus vecinos en $P$. Supongamos que los vecinos son $$N(v_0) = \{v_{i_1},\ \cdots,\ v_{i_\ell}\}$$ donde $\ell = \deg(v_0)$. Por lo tanto, tenemos el ciclo $$C=(v_0,\ v_1,\ \cdots,\ v_{i_\ell}, v_0)$$ Sabemos que $$i_\ell \ge \ell=\deg(v_0) \ge d$$ así que $C$ tiene una longitud de al menos $d+1$