# 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?

-
I'm either being dumb, or there's something peculiar here. If there were some vertex other than $x_1,\ldots,x_k$ in $N(x_1)\cup N(x_k)$, then appending it to the path (before $x_1$ if it lies in $N(x_1)$, after $x_k$ if it lies in $N(x_k)$) would yield a longer path; the edge cannot already be in use, because one of the endpoints is not in the set of vertices being used. I don't see why the degree of the vertices comes into play here... – Arturo Magidin Jun 25 '11 at 5:20
@Arturo Magidin What I don't understand is how the path would change after I append a new vertex from the Neighbor. Edit: sorry I changed my question a little. – Mark Jun 25 '11 at 5:25
@Mark: If $y\in N(x_1)$, that means that there is an edge between $y$ and $x_1$; if $y$ is not any of $x_1,\ldots,x_k$, you haven't used this edge. So add $y$, the edge to $x_1$, and then the path you already had. Similar if you have $y\in N(x_k)$ but is not any of $x_1,\ldots,x_k$. Is this by any chance part of a larger problem? – Arturo Magidin Jun 25 '11 at 5:28
@Arturo Magidin I am trying to prove the Dirac Theorem. What I don't understand is that just because I have an edge unused does that mean it has to be part of the longest path? Is there a theorem for this? – Mark Jun 25 '11 at 5:31
@Mark: I'm saying that if you have any path, $P=x_1\cdots x_k$, and $N(x_1)\cup N(x_k)$ contains some vertex that $P$ doesn't go through, then you can obtain a longer path by appending that vertex to the path. By contrapositive, if there is no path longer than $P$, then $P$ cannot be extended, and therefore $N(x_1)\cup N(x_k)$ must contain only vertices that are already in the path $P$. – Arturo Magidin Jun 25 '11 at 5:34

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\}$.

-