Supongamos que hay dos diferentes árboles de expansión para un simple gráfico. Deben tener un borde en común?

Question

Mi instinto es sí, pero no sé cómo se formaliza en una prueba. Todavía no he envuelto mi cabeza alrededor de los árboles de expansión todavía. Todos los pensamientos son apreciados!

Answer 1

La respuesta es no. Considere la posibilidad de este contraejemplo:

Los bordes rojos de forma que los bordes de un árbol de expansión.

El negro los bordes de la forma de los bordes de otro árbol de expansión.

Answer 2

El grafo completo con $5$ verticies proporciona un contraejemplo, usted puede ir "en el exterior" o "alrededor de la estrella".