Pruebas que involucran subárboles de un árbol

Un árbol es un gráfico que está conectado y no contiene ningún ciclo. Desde$T_1 \cap T_2$es un subgrafo de ambos$T_1$y$T_2$, que son árboles, obviamente no puede contener ciclos.

Lo que queda por demostrar es que$T_1\cap T_2$todavía está conectado. Fijar dos vértices$v_1, v_2$en$T_1\cap T_2$. Obviamente, entonces también tenemos$v_1, v_2\in T_1$y$v_1, v_2\in T_2$. Además, supusimos$V_{T_1}\cap V_{T_2}\neq \emptyset$. Sea por lo tanto$v$ser un vértice en$V_{T_1}\cap V_{T_2}$(y por tanto también en los gráficos$T_1$,$T_2$, y$T_1\cap T_2$).

Desde$v_1$y$v$(resp.$v_2$y$v$) están en$T_1$(resp.$T_2$) y$T_1$(resp.$T_2$) están conectados, hay un camino desde$v_1$a$v$(resp. de$v_2$a$v$). Al combinar estos caminos, también tenemos un camino desde$v_1$a$v_2$.

Por lo tanto,$T_1\cap T_2$está conectado, y debido a su ciclo libre, entonces también es un árbol.

Para la segunda afirmación, considere esto:

Si tenemos tres árboles$T_1,T_2,T_3$que son subárboles de un árbol$T$dos de los cuales no son disjuntos, podemos obtener elementos$t_{12}, t_{13}, t_{23}$tal que$t_{ij} \in T_i\cap T_j$. Desde$t_{12},t_{13}\in T_1$,$t_{12},t_{23}\in T_2$, y$t_{13},t_{23}\in T_3$, existen caminos desde$t_{12}$a$t_{13}$dentro$T_1$, de$t_{12}$a$t_{23}$dentro$T_2$, y de$t_{13}$a$t_{23}$dentro$T_3$.

Dado que los árboles están libres de ciclos, el camino desde$t_{12}$a$t_{13}$dentro$T_1$entonces debe ser igual a la de$t_{12}$encima$t_{23}$a$t_{13}$y por lo tanto$t_{23}\in T_1$, y, por supuesto, también$t_{23}\in T_2\cap T_3$y por lo tanto el$T_1\cap T_2\cap T_3 \neq \emptyset$.

Ahora aplicando el lema para dos subárboles dos veces se obtiene que$T_1\cap T_2\cap T_3$es un árbol; para un enfoque más directo,$t_{23}$puede desempeñar el papel del nodo al que todos los demás nodos deben estar conectados, de manera similar a$v$arriba.

EDITAR: Anteriormente pensé que la segunda afirmación era falsa, dando un contraejemplo incorrecto.

La "expansión de la afirmación anterior" es un caso particular del Ejercicio 7 en mi primavera de 2017 Matemáticas 5707 de mitad de período 2 :

Dejar$G = \left(V, E, \phi\right)$sea ​​un multigrafo.

Para cualquier subconjunto$U$de$V$, dejamos$G \left[U\right]$denote el submultigrafo$\left(U, E_U, \phi\mid_{E_U}\right)$de$G$, dónde$E_U$es el subconjunto$\left\{ e \in E \mid \phi \left(e\right) \subseteq U \right\}$de$E$. (De este modo,$G \left[U\right]$es el submultigrafo obtenido de$G$eliminando todos los vértices que no pertenecen a$U$, y luego eliminando todos los bordes que no tienen ambos puntos finales en$U$.) Este submultigrafo$G \left[U\right]$se llama submultigrafo inducido de$G$en el subconjunto$U$.

Dejar$A$,$B$y$C$ser tres subconjuntos de$V$tal que los submultigrafos$G \left[A\right]$,$G \left[B\right]$y$G \left[C\right]$estan conectados.

un ciclo de$G$se llamará ecléctica si contiene al menos una arista de$G \left[A\right]$, al menos un borde de$G \left[B\right]$y al menos un borde de$G \left[C\right]$(aunque no se requiere que estos tres bordes sean distintos).

(a) Si los conjuntos$B \cap C$,$C \cap A$y$A \cap B$no están vacíos, pero$A \cap B \cap C$está vacío, luego demuestre que$G$Tiene un ciclo ecléctico.

(b) Si los submultigrafos$G \left[B \cap C\right]$,$G \left[C \cap A\right]$y$G \left[A \cap B\right]$están conectados, pero el submultigrafo$G \left[A \cap B \cap C\right]$no es conexo, luego demuestre que$G$Tiene un ciclo ecléctico.

[ Nota: Tenga en cuenta que el multigrafo con$0$los vértices no cuentan como conectados.]

(Por qué este ejercicio en realidad generaliza la afirmación se explica después de la solución del ejercicio. No estoy dando un número de teorema, ya que ese número va a cambiar).