He conseguido demostrar la segunda parte - que un árbol que tiene un vértice de grado n-1 y todos los demás están conectados a él - el grafo complemento de dicho árbol es un vértice aislado y el resto de los vértices forman un grafo completo.
Ahora, no puedo llegar a demostrarlo para la otra opción - es decir, si cada vértice del árbol es de grado $1\leq d(v) < n-2$ que el gráfico del complemento está conectado.
Supongamos que el gráfico no está conectado. Entonces, separa el gráfico en 2 gráficos distintos. Ahora, todas las aristas que faltan entre los 2 componentes deben haber pertenecido al árbol. Supongamos que el tamaño de los 2 componentes es a y b. (el tamaño de un componente se refiere al número de vértices en él).
Entonces, tenemos : $$ a + b = n $$ y $$ a*b \le (n-1) $$ (porque el número de aristas de un árbol no puede ser mayor).
La única manera de que esto ocurra es cuando a=n-1 y b=1 , que es la segunda parte de tu pregunta.
La otra respuesta es agradable - esto es sólo una alternativa.
Dejemos que $T$ sea un árbol y $\overline{T}$ sea su complemento. Supongamos que en $\overline{T}$ hay vértices $a,b, c$ tal que $a$ no está en el mismo componente que $b$ y $c$ y que $b$ y $c$ no comparten ningún borde. Entonces $a,b,c$ forman un triángulo en $T$ y no puede ser un árbol. Por lo tanto, $\overline{T}$ tiene como máximo 2 componentes $X$ y $Y$ y cada uno debe ser una camarilla. Si ambos $|X|, |Y| \geq 2$ , entonces toma $x_1, x_2 \in X$ y $y_1, y_2 \in Y$ . Entonces $T$ tiene el ciclo $x_1y_1x_2y_2x_1$ y no puede ser un árbol. Por lo tanto, al menos uno de $X$ o $Y$ debe ser de tamaño uno, lo que es posible si $T$ es un árbol estrella.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
