Show that every graph $G$ has a path of length $\delta(G)$ A path in a graph is a subgraph isomorphic to $P_n$, for some $n$. The length of a path is its number of edges. Prove that every graph $G$ has a path of length $\delta(G)$, where $\delta(G)$ is the minimum degree of $G$.

Let $P$ be the longest path in $G$ from $v_0$ to $v_k$. As min degree is $\delta(G)$, this path contains every neighbor of $v_k$ are on this path and if it is not like this, then let us assume that there is a vertex $v_j$ neighbor of $v_k$ not in the path. then add this to the given path. and thus we get a path of longer length than $P$. A contradiction
