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$.
closed as not constructive by Andrés E. Caicedo, Micah, Lord_Farin, Joe, Dennis Gulko Apr 25 '13 at 16:41
As it currently stands, this question is not a good fit for our Q&A format. We expect answers to be supported by facts, references, or expertise, but this question will likely solicit debate, arguments, polling, or extended discussion. If you feel that this question can be improved and possibly reopened, visit the help center for guidance. If this question can be reworded to fit the rules in the help center, please edit the question.
I hope its a simple graph. Let $P$ be the maximal path in the graph $G$. On the contrary assume $|P|\le\delta(G)$.
Suppose $v\in V(P)$ be an endpoint in the path. As $v$ is adjacent to $\delta(G)$ vertices. All of its neighbours can't be in the path $P$. But then its contradicts the fact that its the maximal path.
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