edited by
612 views
2 votes
2 votes
Let $G$ be a graph in which each vertex has degree at least $k$. Show that there is a path of length $k$ in $G$—that is, a sequence of $k+1$ distinct vertices $v_0, v_1, \dots , v_k$ such that for $0 \leq i < k,$ $v_i$ is connected to $v_{i+1}$ in $G$.
edited by

2 Answers

Best answer
3 votes
3 votes
Let us assume $M$ be the maximal path in the graph $G$ and $v$ be the endpoint of $M$. Since the degrees of each vertex in the graph $G$ is equal to $k$  so the degree of $v$ is also $k.$

Now, $M$ is the maximal path of $G$ so, we cant extend the path $M.$ Thus all the $k$ neighbors of $v$ are in $M$. So, the path $M$ contains $(k+1) $points and the path $ M $ is of length $k$. Thus there exists a path of length $k$ in graph $G$.
selected by

Related questions