1
$\begingroup$

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?

  • 0
    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...2011-06-25
  • 0
    @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.2011-06-25
  • 0
    @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?2011-06-25
  • 0
    @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?2011-06-25
  • 0
    @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$.2011-06-25
  • 0
    @Mark: The reason I ask if this is part of a larger problem is that your condition on the degree of the vertices is not used in the argument above. So either I'm doing something dumb, or else that condition is used in a different part of the argument/problem.2011-06-25
  • 0
    @Arturo Magidin "...any path, $P=x1⋯xk$, and $N(x1)∪N(xk)$ contains some vertex that $P$ doesn't go through, then you can obtain a longer path by appending that vertex to the path..." This is what I am confused about, it seems obvious but I don't know how to prove it. Is possible to prove this using simple definitions?2011-06-25
  • 0
    @Mark: I don't know what definitions you are using, but I've used one I know in my answer. It *really is* very simple; if you are confused because it seems too easy, rest assured that this part of the argument *is* easy.2011-06-25

1 Answers 1

6

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