En un árbol, que las rutas entre los vértices $a\to b$ y y $c\to d$ sean vértice-disjuntos. Demuestre que $a\to c$ y $b \to d$ tienen vértices en común.

Question

Que la ruta entre $u$ y $v$ en un grafo simple y conexo sea la secuencia más corta de vértices, tal que $[u,u_1,...,u_n,v]$ sería una forma de recorrer un gráfico desde el vértice $u$ a $v$ .

En un árbol, que las rutas entre los vértices $a\to b$ y y $c\to d$ sean vértice-disjuntos. Demuestre que $a\to c$ y $b \to d$ tienen vértices en común.

Aquí está el boceto de mi intento.

Supongamos por el contrario que $a\to c$ y $b \to d$ son también vértices disjuntos.

Inspeccionemos las rutas $a \to b$ y $a \to c$ . Pueden tener algunos vértices en común, pero deben agotarse en algún momento, de lo contrario $a \to c$ y $c \to d$ se cruzarían, así que la ruta debe ser así:

Es decir, que durante un tiempo las rutas son las mismas, pero luego divergen. El pensemos en $c \to d$ y $a \to c$ también pueden tener un vértice es común, pero porque $c \to d$ y $a \to b$ son disjuntos tiene que caer "por debajo" $A'$ lo que significa que se parece un poco a esto:

Un razonamiento similar nos lleva a encontrar $B'$ y $D'$ lo que significa que tendremos cuatro vértices $A',B',C',D'$ que estará en un ciclo, lo que significa que el gráfico no puede ser un árbol.

¿Es correcto mi razonamiento?

Answer 1

Su razonamiento es esencialmente correcto. Si quieres que sea más preciso (para no tener que decir cosas como "'por debajo' $A^\prime$ " o se basan en imágenes posiblemente engañosas), se puede cambiar un poco la prueba. Lo que sigue es no realmente diferente a su razonamiento, sino simplemente una forma diferente y quizás más precisa de expresarlo.

En primer lugar, argumentar (como lo hizo) que hay un vértice $A^\prime$ donde los caminos $a\rightarrow c$ y $a\rightarrow b$ divergir. Entonces argumentar que los vértices $A^\prime$ , $b$ , $c$ y $d$ satisfacer el mismas condiciones sobre la separación de vértices como $a, b, c, d$ porque los caminos están estrictamente contenidos en los caminos originales. Además, $A^\prime\rightarrow b$ y $A^\prime \rightarrow c$ sólo tienen el vértice $A^\prime$ en común por la elección de $A^\prime$ .

Ahora, en lugar de tener que hacer dibujos cada vez más complicados, puedes aplicar la exactamente lo mismo argumento para $A^\prime$ , $b,c,d$ con $b$ como vértice de interés en lugar de $a$ , obteniendo $B^\prime$ y así sucesivamente.

Aplicando esto un total de cuatro veces, se tiene entonces que $A^\prime, B^\prime, C^\prime, D^\prime$ tienen las siguientes propiedades: $A^\prime\rightarrow B^\prime$ y $C^\prime \rightarrow D^\prime$ son vértice-disjuntos, $A^\prime\rightarrow C^\prime$ y $B^\prime \rightarrow D^\prime$ son disjuntos en sus vértices, y cada par de caminos consecutivos (por ejemplo $A^\prime \rightarrow B^\prime$ y $B^\prime \rightarrow C^\prime$ ) sólo tienen un vértice en común. Entonces es fácil verificar que $A^\prime\rightarrow B^\prime \rightarrow C^\prime \rightarrow D^\prime \rightarrow A^\prime$ es de hecho un ciclo.