Caminhos e ciclos

Um caminho é uma sequência $\langle v_1, \ldots, v_n\rangle$ de vértices onde cada $\{v_i, v_{i + 1}\}$ é uma aresta (todas as arestas são distintas). Um caminho é dito simples se cada vértice aparece no máximo uma vez. O comprimento de um caminho é a quantidade de arestas deles (ou seja, $n$ no nosso exemplo).

1 Mostre que todo grafo $G$ admite um caminho de comprimento pelo menos $\delta(G)$.

Um ciclo é um caminho $\langle v_1, \ldots, v_n, v_{n + 1}\rangle$ onde $v_{n + 1} = v_1$.