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...x_k$ be a longest path in $G$. Show that $N(x_1)$ $\bigcup$ $N(x_k)$ $\subseteq$ {$x_1,...,x_k$}.

What does $N(x_1)$ $\bigcup$ $N(x_k)$ mean in this context? It's not explained anywhere in notes or class.

1 Answers 1

5

It means the set of neighbors of the vertex: $N(x)=\{{ v\in V(G):\{v,x\}\in E(G)\}}$