Problema en teoría de grafos: $\deg(v)\geq\frac{|V(G)|}{2}$

Question

Sea $G$ sea un grafo tal que $\forall v\in V(G)$ , $\deg(v)\geq\frac{|V(G)|}{2}$ .

Sea $p = x_1x_2\dots x_k$ sea el camino más largo en $G$ . Demuestre que $N(x_1)\cup N(x_k)\subseteq \{x_1,...,x_k\}$ .

¿Es el principio del encasillamiento el mejor camino?

Answer 1

La condición de que cada vértice tenga al menos un grado $n/2$ ( $n$ el número de vértices) es irrelevante para esta afirmación.

¿Qué es un camino en un grafo? Es una secuencia $(x_1,e_1,x_2,e_2,\ldots,e_{k-1},x_k)$ donde $x_1,\ldots,x_k$ son vértices, $e_1,\ldots,e_{k-1}$ son bordes, $e_i$ se une a $x_i$ y $x_{i+1}$ . Asumiré además que el $e_i$ son distintos por pares (aunque pueden unir los mismos vértices si el grafo tiene múltiples aristas). Si las aristas se entienden por el contexto, podemos escribir esto simplemente como $x_1x_2\cdots x_k$ .

Si $G$ es un gráfico y $v$ es un vértice, entonces $N(v)$ es el conjunto de todos los vértices $w$ de $G$ para el que existe una arista entre $w$ y $v$ .

Ahora dejemos que $P=(x_1,e_1,x_2,e_2,\ldots,e_{k-1},x_k)$ sea un camino en $G$ . Supongamos que $y\in N(x_1)-\{x_1,\ldots,x_k\}$ . Desde $y$ está en $N(x_1)$ entonces existe una arista $f$ que une $y$ y $x_1$ . Además, puesto que $y$ no está en $\{x_1,\ldots,x_k\}$ , $f\neq e_j$ para $j=1,\ldots,k-1$ (ya que una arista es incidente en sólo dos vértices, y no hay $e_j$ es incidente en $y$ ). Por lo tanto, $$P' = (y,f,x_1,e_1,x_2,e_2,\ldots,e_{k-1},x_k)$$ también es una ruta en $G$ .

Del mismo modo, si existe $y\in N(x_k)-\{x_1,\ldots,x_k\}$ y $f$ es una arista que une $x_k$ y $y$ entonces $$P' = (x_1,e_1,x_2,e_2,\ldots,e_{k-1},x_k,f,y)$$ es una ruta en $G$ .

En particular, si $P=(x_1,e_1,x_2,e_2,\ldots,e_{k-1},x_k)$ es una ruta en $G$ y $N(x_1)\cup N(x_2)$ no está contenido en $\{x_1,\ldots,x_k\}$ entonces hay un camino en $G$ más largo que $P$ .

Por contraposición, si $P$ es un camino de longitud máxima en $G$ entonces debemos tener $N(x_1)\cup N(x_2)\subseteq \{x_1,\ldots,x_k\}$ .