I have one general question considering graph theory. If we have that minimal degree of node in graph is $\ge k$ than G has path length $\ge k$. I saw this example on this site already, but I have one question. If we guess that longest path in graph is length r $v_0v_1\cdots v_r$ then $d(v_0)\ge k$. And how we know that every neighbor of $v_0$ is inside this path? If I know definition of path, than every node has degree 1 or 2, so if $k\ge 2$ this shouldn't be true, right? So my question is how we can know that every neighbor of $v_0$ is inside path? PS, also I saw that if we add one node that is not neighbor of $v_0$ then we get longer path which is contradiction, but again how we can claim that if $k\ge 4$ then all 4 neighbors of $v_0$ are inside path when we can only have 1 or 2 as degrees of node in path
Longest path in graph
graph theory
Related Solutions
Let $P_1 = \langle v_0, \dots, v_m \rangle$ and $P_2 = \langle u_0, \dots, u_n \rangle$, such that $P_1$ and $P_2$ have no common vertices, be two different longest inextensible paths in a graph. Let us assume that $m \ge n$. Furthermore, let $v_k$ and $u_l$ be connected (in the original graph) be a path $\langle v_k, w_1, \dots, w_p, u_l \rangle$ such that neither of $w_i$ belong to either $P_1$ or $P_2$ (the length of such path is, obviously, $p+1$).
Without the loss of generality, we can assume that $k \ge m/2$ and $l \ge n/2$. This is just a matter of notation: we're labeling vertices in a way that $\langle v_0, \dots, v_k \rangle$ is longer than or equally long as $\langle v_k, \dots, v_m \rangle$ and that $\langle u_1, \dots, u_l \rangle$ is longer than or equally long as $\langle u_l, \dots, u_n \rangle$.
We construct a new path $$P := \langle v_0, \dots, v_k, w_1, \dots, w_p, u_l, \dots u_0 \rangle$$ which has length $$k + (p + 1) + l \ge m/2 + p + 1 + n/2 \ge n/2 + p + 1 + n/2 = n + p + 1 > n, $$ so $P$ is strictly longer than $P_2$ (and obviously different from $P_1$), which is a contradiction with the assumption that $P_2$ is the second longest inextensible path in the graph.
It is not generally true of a path of maximum length that all of any vertices neighbors need be included in the path. For a counter example, consider a path of maximum length on a caterpillar.
What is true of a path of maximum length in any graph: both of the end vertices of the path have their neighbors completely in the path.
Assume otherwise, that an end vertex $u$ has some neighbor not on the path, say $v$, then the original path plus the edge $uv$ is a path of greater length.
Hopefully this clears up your understanding. I would go back to the proof you were quoting and make sure that $u$ is an end vertex. If not, then the proof has a problem.
Best Answer
There are two things that can be called paths. One is a path graph, which is a graph that looks like
in which every vertex does in fact have degree $1$ or $2$. Another one is a path inside another graph. These can be defined as a sequence of vertices, or as a sequence of vertices and edges, but they always correspond to subgraphs of your original graph that are isomorphic to the path graph.
So if you have a graph $G$ with minimum degree $k$, and you've found a longest path $P$ inside $G$, then $P$ gives us a subgraph in which every vertex has degree $1$ or $2$. However, in $G$ as a whole, those vertices have degree $k$ or more. It's not even necessarily an induced subgraph: there might be other edges between the vertices in the path, which are not part of the path graph.
And that's what happens when you look at this vertex $v_0$ in the path $v_0, v_1, v_2, \dots, v_r$. In the path subgraph, it has degree $1$. In $G$ as a whole, it has degree $k$ or more.
If $v_0$ were adjacent to any vertex not on the path, we could extend the path. This is a contradiction if we chose the path to be the longest path there is.
So $v_0$ must have at least $k$ neighbors in $G$ as a whole among $\{v_1, v_2, \dots, v_r\}$, even though only one of those, $v_1$, is $v_0$'s neighbor in the path subgraph.