# Show that every graph $G$ has a path of length $\delta(G)$ [closed]

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$.

• Also, I think it's impolite to disregard suggestions on how to improve your question (such as those here). Commented Apr 23, 2013 at 14:12

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

• I wish people wouldn't answer questions, when the person asking the question has put in no effort beyond copying the question out of a problem set. Commented Apr 23, 2013 at 13:31

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.

Hence $|P|\ge\delta(G)+1$.

• I think you need to choose $v$ to be the end vertex of the path.
– Easy
Commented Apr 23, 2013 at 11:49
• Yeah, I edited it. Commented Apr 23, 2013 at 11:57
• I wish people wouldn't answer questions, when the person asking the question has put in no effort beyond copying the question out of a problem set. Commented Apr 23, 2013 at 13:31