probar el grafo G con n vértices, vértice de grado n−1n−1n-1 y resto de vértices de grado 111 es un grafo de árbol

Soy un estudiante discreto de matemáticas y me he topado con la siguiente pregunta. Traté de demostrarlo y específicamente en la primera parte pensé en dos formas de demostrarlo. pero en cada una de las formas, la prueba se ve muy corta sin mucha información, así que me temo que olvidé algo o hice algo mal. agradeceria sus consejos y ayuda

"sea G un grafo simple sobre los vértices {1,2,...,n} mientras que$n\ge3$y$n\in N$. además, el vértice número 1 es de grado$n-1$y todos los demás vértices son de grado 1. Demuestre que G es un gráfico de árbol.

Prueba:

1. Demostrar que G es un gráfico conexo: observemos que el gráfico es un "gráfico de estrella" porque el gráfico es simple (es decir, sin bucles y múltiples aristas) y el primer vértice es de grado$n-1$, mientras que hay n vértices. es decir, el vértice del grado$n-1$está conectado con el resto de$n-1$vecinos Entonces, como vemos, hay un camino entre cada dos vértices en G -> G es un gráfico conectado.

   • otra forma en la que pensé: del teorema de los grados:$2|E|=\Sigma v_i=(n-1)*[1]+[n-1]=2n-2 \to |E|=n-1$y hay un teorema que dice que un grafo con n vértices y n-1 aristas es un grafo conexo.

2. Demostrar que G es un grafo sin ciclos: notemos que G es isomorfo a un grafo bipartito mientras que los vértices de grado 1 son el grupo A de vértices y el vértice de grado$n-1$es el grupo B de vértices. y hay un teorema que dice que todo grafo bipartito es un grafo acíclico.

de 1 y 2 obtenemos que G es un grafo acíclico y conexo. entonces por definición de árbol, G es un gráfico de árbol.