Mostrar que cada gráfico de $G$ tiene un camino de longitud $\delta(G)$

Question

Un camino en un grafo es un subgrafo isomorfo a $P_n$, para algunas de las $n$. La longitud de un camino es el número de sus bordes. Demostrar que todo grafo $G$ tiene un camino de longitud $\delta(G)$ donde $\delta(G)$ es el mínimo grado de $G$.

Answer 1

Yo espero que un simple gráfico. Deje $P$ ser la máxima de la ruta de acceso en el gráfico de $G$. Por el contrario asumen $|P|\le\delta(G)$.

Supongamos $v\in V(P)$ ser una estación en el camino. Como $v$ es adyacente a $\delta(G)$ vértices. Todos sus vecinos no pueden estar en el camino de $P$. Pero luego su contradice el hecho de que la máxima de la ruta.

Por lo tanto $|P|\ge\delta(G)+1$.

Answer 2

Deje $P$ ser el camino más largo en $G$$v_0$$v_k$. Como min grado es $\delta(G)$, esta ruta de acceso contiene todos los vecinos de $v_k$ están en este camino y si no es así, entonces, supongamos que hay un vértice $v_j$ vecino de $v_k$ no en el camino. a continuación, añadir esto a la ruta dada. y así llegamos a un camino de mayor longitud de $P$. Una contradicción