Problem in graph theory: $\deg(v)\geq\frac{|V(G)|}{2}$ Let $G$ be a graph such that $\forall v\in V(G)$, $\deg(v)\geq\frac{|V(G)|}{2}$.
Let $p = x_1x_2\dots x_k$ be a longest path in $G$. Show that $N(x_1)\cup N(x_k)\subseteq \{x_1,...,x_k\}$.
Is using the pigeonhole principle the best way to go?
 A: The condition that each vertex has degree at least $n/2$ ($n$ the number of vertices) is irrelevant to this claim.
What is a path in a graph? It is a sequence 
$(x_1,e_1,x_2,e_2,\ldots,e_{k-1},x_k)$, where $x_1,\ldots,x_k$ are vertices, $e_1,\ldots,e_{k-1}$ are edges, $e_i$ joins $x_i$ and $x_{i+1}$. I will further assume that the $e_i$ are pairwise distinct (though they may join the same vertices if the graph has multiples edges). If the edges are understood from context, then we can write this simply as $x_1x_2\cdots x_k$. 
If $G$ is a graph and $v$ is a vertex, then $N(v)$ is the set of all vertices $w$ of $G$ for which there is an edge between $w$ and $v$. 
Now let $P=(x_1,e_1,x_2,e_2,\ldots,e_{k-1},x_k)$ be a path in $G$. Suppose that $y\in N(x_1)-\{x_1,\ldots,x_k\}$. Since $y$ is in $N(x_1)$, then there exists an edge $f$ that joins $y$ and $x_1$. Moreover, since $y$ is not in $\{x_1,\ldots,x_k\}$, $f\neq e_j$ for $j=1,\ldots,k-1$ (since an edge is incident in only two  vertices, and no $e_j$ is incident in $y$). Thus,
$$P' = (y,f,x_1,e_1,x_2,e_2,\ldots,e_{k-1},x_k)$$
is also a path in $G$.
Similarly, if there exists $y\in N(x_k)-\{x_1,\ldots,x_k\}$, and $f$ is an edge that joins $x_k$ and $y$, then
$$P' = (x_1,e_1,x_2,e_2,\ldots,e_{k-1},x_k,f,y)$$
is a path in $G$.
In particular, if $P=(x_1,e_1,x_2,e_2,\ldots,e_{k-1},x_k)$ is a path in $G$, and $N(x_1)\cup N(x_2)$ is not contained in $\{x_1,\ldots,x_k\}$, then there is a path in $G$ that is longer than $P$.
By contrapositive, if $P$ is a path of maximal length in $G$, then we must have $N(x_1)\cup N(x_2)\subseteq \{x_1,\ldots,x_k\}$. 
