Árboles que son isomorfos a un subgrafo de un grafo G.

Question

Tengo una prueba de teoría de grafos que me han aconsejado hacer por inducción pero estoy teniendo un poco de problemas para completar el paso de inducción.

La pregunta es: Sea T un árbol sobre k vértices. Demostrar que si G es un grafo donde cada vértice tiene grado al menos k-1, entonces T es isomorfo a algún subgrafo de G.

Hasta ahora lo he hecho:

1) Comprueba que n=1 funciona. Si n=1 entonces todos los árboles son vértices, que van a ser isomorfos a algún subgrafo de G.

2) Supongamos que se mantiene n=k. Esto significa que tenemos un árbol en k vértices que es isomorfo a algún subgrafo de G, donde G es un grafo donde cada vértice tiene grado al menos k-1.

3) Ahora comprueba si se cumple el caso n=k+1. Ahora tenemos un árbol en k+1 vértices y un grafo donde cada vértice tiene grado al menos k...

¿Cómo puedo demostrar que el paso de inducción (3) es válido?

Answer 1

Sabes que en tu gráfico $G$ con cada vértice de grado al menos $k$ existe un subgrafo isomorfo al árbol $T_{k}$ . Todo lo que necesitamos ahora es un vértice más en $G$ para adherirse a $T_k$ que no esté ya contenida en $T_k$ .

Examinar los vértices adyacentes a algún punto final $t$ del árbol $T_k$ . ¿Cómo sabemos que debe haber un vértice adyacente a $t$ no contenida en $T_k$ ?