Demostrando distancia entre cualquier dos vértices es a lo más 2.

Question

Si hay $n$ vértices y al menos $\frac{1}{2}(n-1)$ grados de cada vértice, ¿cómo demostrar que la distancia entre cualquier dos vértices es 2 más? He intentado dibujar unos gráficos con diferentes valores de $n$ pero yo no estoy seguro de cómo probar todos $n$.

Answer 1

Recoger cualquier % dos vértices $v_1$y $v_2$ en el gráfico. Si están conectados por un borde, su distancia es $1$ y hemos terminado. Si no hay vértices de $n-2$ $v_1$ y $v_2$ para conectar. Que $E_1$ $E_2$ ser el conjunto de vértices conectados a $v_1$ y $v_2$ respectivamente. Se nos da %#% $ de #% esto implica

$$|E_1| \ge \frac12(n-1)\quad\text{ and }\quad |E_2| \ge \frac12(n-1)$ $ Esto significa$$ |E_1 \cap E_2| = |E_1| + |E_2| - |E_1 \cup E_2| \ge \frac12(n-1) + \frac12(n-1) - (n-2) > 0$. Elegir un$E_1 \cap E_2 \ne \emptysetv$y conectar$E_1 \cap E_2$y$v_1$por un camino de longitud$v_2$($2$). En este caso, la distancia entre$v_1 \to v \to v_2$y$v_1$es$v_2$.

Answer 2

Supongamos que la distancia de $V_1$ y $V_2$ es mayor que $2$. ¿Qué pasaría?

• $\deg{V_1} \geq \frac12 (n-1)$, Hay al menos $\frac12 (n-1)$ vértices conectados directamente a $V_1$.
• Estos no pueden ser conectados a $V_2$, otra cosa que hemos encontrado un camino de longitud $2$.
• Pero $V_2$ $n-1$ vértices a elegir entre tener un borde. Algunos no están permitidos. ¿Que? Así, el $\frac12 (n-1)$ los vértices desde antes. Y $V_1$ sí mismo. ¡Así $$ \deg{V_2} \leq (n-1) - \frac12 (n-1) - 1 = \frac12 (n-1) - 1 < \frac12 (n-1). contradicción!

Answer 3

Que $x$ $y$ ser dos vértices no adyacentes en un gráfico simple $G$. Mostramos que $x$ y $y$ tienen un vecino común. Si $G$ es simple, entonces la colección de verties adyacentes a $x$, llamar al $N(x)$, tiene tamaño por lo menos $(n-1)/2$. Del mismo modo, $|N(y)|\geq (n-1)/2$. También $|N(x)\cup N(y)|\leq n-2$ $x$ y $y$ no son adyacentes. Pero $$| N (x) N(y) \cap | = | N(x) | + | N(y) |-| \Cup N (x) N (y) | \geq 1$$ como se desee.