Longest path in a graph. How do I prove that the longest path in a graph that starts from the vertex $\ v_1 $, includes all the adjacent vertices of $\ v_1 $?
You claim:


  For every vertex $v_1$, the longest path that starts in $v_1$ includes all adjacent vertices of $v_1$


This is false. If you have a graph with four vertices, $a,b,cd$, and three edges, $(a,b)$, $(b,c)$, $(c,d)$ then the longest path that starts at $b$ is the path $b\to c\to d$ and it does not include $a$.
Let $P$ be a longest path in the graph that stars at vertex $v_1$. We will prove that $P$ contains all neighbours of $v_1$. Suppose not. Then, there is a vertex $v_2$ adjacent to $v_1$ such that $P$ does not contain $v_2$. But that implies that we can join path $P$ with path $v_1v_2$, obtaining a path longer than $P$, a contradiction to the fact that $P$ is a longest path.