Árbol de expansión con conjunto de desconexión

Question

¿Cómo enfoco este problema?

Supongamos que$G$ es un gráfico conectado y$e_1$ y$e_2$ son sus bordes de tal manera que cada árbol de expansión de$G$ contiene al menos uno de ellos. Demuestre que$\left\{e_1,e_2\right\}$ forma un conjunto de desconexión para$G$.

Answer 1

Suponga que no son un conjunto de desconexión para$G$ y elimínelos para crear el gráfico conectado$G'$. Tome un árbol de expansión para$G'$ y demuestre que esto le da un árbol de expansión para$G$, lo que contradice la hipótesis de que dicho árbol debe contener uno de esos bordes.