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
    @Mark: I don't know what de$f$initions you are using, but I've used one I know in my answer. It *really is* very simple; i$f$ you are con$f$used 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\}$.