Demostrar el número de aristas de un árbol de expansión de aristas disjuntas

Question

Tengo el siguiente problema. No son deberes, es un trabajo adicional que quiero hacer para comprender mejor el material de mi clase de Combinatoria.

Demuestre que si un gráfico $G$ contiene $k$ árboles de expansión de aristas disjuntas, entonces para cada partición ( $V_1$ , $V_2$ , ..., $V_n$ ) de $V(G)$ el número de aristas de $G$ que tienen extremos en diferentes partes de la partición es al menos $k(n-1)$ .

Answer 1

Para cada árbol de expansión (y debido a su definición) debe existir (al menos) una arista que conecte $V_1$ a algunos $V_j$ con $j\ne1$ . Sin pérdida de generalidad se puede suponer $j=2$ . Pero ahora debe haber algún borde que conecta $V_1\cup V_2$ a algunos $V_j$ con $j\notin\{1,2\}$ , de nuevo asumir $k=3$ . Puedes seguir con este proceso hasta que tengas todos los $V_i$ s conectado (soy perezoso y dejaré la inducción rigurosa completa para usted).

Al final tienes $n-1$ aristas para cada árbol de expansión, y como no hay dos árboles de expansión que compartan una arista, se puede estar seguro de que todos son diferentes. Por último, como hay $k$ spanning trees se tiene que el número de aristas de $G$ que tienen extremos en diferentes partes de la partición es al menos $k(n-1)$ .