Longest path in graph 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
 A: There are two things that can be called paths. One is a path graph, which is a graph that looks like
v1 --- v2 --- v3 --- ... --- vn

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.
