Conexión entre dos árboles

Dado un árbol T 1 = ( V 1 , mi 1 ) (así que un gráfico no dirigido acíclico conectado es la definición con la que estoy trabajando) y otro árbol T 2 = ( V 2 , mi 2 ) , es cierto que dado cualquier nodo v ∈ V 1 en T 1 y tu ∈ V 2 en T 2

T := ( V 1 ∪ V 2 , mi 1 ∪ { v , tu } ∪ mi 2 )
¿Sigue siendo un árbol? Estoy muy convencido de que es cierto, pero no puedo demostrarlo con rigor, alguien podría darme una pista o un contraejemplo si es falso. Gracias.

Editar: V 1 ∩ V 2 = ∅ .

Te refieres a v ∈ V 1 , tu ∈ V 2 , ¿no?

Respuestas (3)

Sugerencia: si el vértice se establece V 1 , V 2 son disjuntos, luego agregando un borde { tu , v } entre los dos árboles hace que el gráfico compuesto sea un árbol. Demostrar aciclicidad y conectividad.

Como eliminar cualquier borde de un árbol da como resultado exactamente dos árboles, su conjetura es verdadera (para árboles disjuntos).

Además, el gráfico A no tiene ciclos, y tampoco el gráfico B. Por lo tanto, un ciclo debe viajar del gráfico A al gráfico B y viceversa, pero solo hemos proporcionado un nuevo borde para hacer esto.

Contraejemplo:

V 1 = V 2 = { 1 , 2 , 3 } , mi 1 = { { 1 , 2 } , { 1 , 3 } } , mi 2 = { { 1 , 2 } , { 2 , 3 } } , tu = 2 , v = 3

Gracias mi pregunta estaba mal planteada, V 1 ∩ V 2 = ∅ , voy a editar.
Conexión entre dos árboles
RespuestasAquíPolítica de privacidad1y, 0v