Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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
up vote 6 down vote accepted

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.