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$.
Respuestas
¿Demasiados anuncios?
Joe Gauterin
Puntos
9526
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 \emptyset$ $v$ 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$.
Kezer
Puntos
46
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!
Foobaz John
Puntos
276
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.
