¿Alguno de los dos árboles de expansión de un gráfico simple siempre tiene algunas aristas comunes?

Intenté algunos casos y descubrí que dos árboles de expansión de un gráfico simple tienen algunos bordes comunes. Quiero decir que no pude encontrar ningún contraejemplo hasta ahora. Pero tampoco pude probar o refutar esto. ¿Cómo probar o refutar esta conjetura?

No, considere el gráfico completo :$K_4$

Tiene los siguientes árboles de expansión de borde disjunto:

Para los lectores más interesados, hay algunas investigaciones sobre la descomposición del gráfico en árboles de expansión separados por bordes .

Por ejemplo, los trabajos clásicos sobre el problema de descomponer un gráfico en factores conectados$n$ por WT Tutte y arboles que se separan de bordes de gráficos finitos de C. St.JA Nash-Williams proporciona una caracterización de gráficos que contiene pares de bordes disjuntos que abarca árboles$k$

Por ejemplo, el papel de las descomposiciones bicíclicas de gráficos completos en árboles de expansión por Dalibor Froncek muestra cómo descomponer gráficos completos en árboles de expansión isomorfos .$K_{4k+2}$${2k+1}$

Por ejemplo, las Factorizaciones en papel de gráficos completos en árboles de expansión con todos los grados máximos posibles de Petr Kovář y Michael Kubesa muestran cómo factorizar para abarcar árboles con un grado máximo dado.$K_{2n}$

Puedes buscar más. Por ejemplo, una búsqueda en Google para la descomposición del gráfico en árboles de expansión .

EDITAR: Esto es incorrecto como se señala en los comentarios. Como dice la otra respuesta, se puede hacer un árbol de expansión para sin compartir bordes.$K_4$

No, no es cierto que dos árboles de expansión de un gráfico tengan bordes comunes.

Considere el gráfico de la rueda:

Puede hacer un árbol de expansión con bordes "dentro" del bucle y otro desde el bucle exterior.

Después de observar los gráficos presentados por @Bjorn y @Gokul, llego a la conclusión de que cada gráfico completo con tiene al menos dos árboles de expansión con bordes disjuntos.$K_n$$n\geq4$

La gráfica dada en la imagen, que es rueda, tiene claramente dos árboles que se extienden con bordes disjuntos. De hecho, cada rueda tendrá exactamente árboles que se extienden con bordes desunidos porque uno es un gráfico complementario del otro.$2$

Ahora, si miramos la solución de @Bjorn cuidadosamente, encontramos que su gráfico y árboles de expansión son homomórficos a los gráficos que se muestran en la imagen. De hecho, cada gráfico completo con tiene rueda como su subgrafo, por lo que se deduce directamente que cada gráfico completo completo con tiene al menos 2 (¿o exactamente ?) Que abarcan árboles con bordes disjuntos.$K_n$$n\geq4$$n\geq4$$2$

PD : Esta observación da lugar a preguntas más interesantes.$2$

1. ¿Hay algún gráfico completo con más de árboles de expansión con bordes disjuntos? O siempre tendrá exactamente árboles de expansión con bordes disjuntos.$2$$2$
2. ¿Hay algún gráfico que no sea rueda o rueda como su subgrafo que tiene árboles que se extienden con bordes desunidos?

Para , creo que$K_{2k}$

para son contraejemplos. Es decir, para el primer gráfico, tome los vértices con índices pares y conéctelos al siguiente vértice, y para todos menos el último vértice par, conéctelo también al vértice después de eso. Para el segundo gráfico, haz esto con vértices impares.$0\leq i < k$

E inductivamente, una vez que tenemos un contraejemplo para vértices, es fácil construir un contraejemplo con vértices conectando el nuevo vértice con un borde para un gráfico y con otro borde para el otro.$n$$n+1$

Si el gráfico tiene un puente (es decir, un borde cuya eliminación desconecta el gráfico), entonces este borde debe pertenecer a cada árbol de expansión. Intuitivamente, un puente es el único borde que conecta sus dos puntos finales y, por lo tanto, necesariamente pertenece a cada subgrafo conectado.

Por otro lado, si un borde del gráfico pertenece a un ciclo, entonces existe un árbol de expansión que no contiene este borde.

Entonces, si cada borde de un gráfico pertenece a un ciclo, entonces ningún borde es común a todos los árboles de expansión (es decir, la intersección de los conjuntos de bordes de los árboles de expansión es el conjunto vacío).