Gráficos de bosque$F_1$ y$F_2$ con los mismos vértices pero bordes diferentes. Demuestra que hay un borde donde$F_1$ con él sigue siendo un bosque

Question

Estoy teniendo un momento bastante difícil con esta pregunta, he estado pensando en ello por unas horas y no tengo ni idea de cómo empezar a probar esto, porque es trivial, pero demostrando que ha sido difícil para mí.

Dado dos bosques$F_1 = (V,A)$ y$F_2 = (V,B)$ con el mismo grupo de vértices$V$. También se da que$|B| > |A|$. Demuestre: existe un borde$e \in B \backslash A$ donde$F_1 \cup \{e\}$ sigue siendo un bosque.

¡Cualquier ayuda será apreciada!

Answer 1

Sugerencia: El hecho de que $|B|>|A|$ puede ser usado para demostrar que $F_1$ no está conectado. ¿Por qué hace esto implica que tal un borde existe?

Algunos de los más comentarios: Este es un resultado intermedio, de que hay una parte importante de la discusión que requiere que no haya conectividad (o algo equivalente) para hacer el trabajo.

Observe que, en general, no hay ningún borde que hace que $F_1$ conectado. Incluso si no es, no podría ser en $B$. Pero no estamos buscando un borde, simplemente una en $B$ que no produce un ciclo en el $A$.

Answer 2

Agregar uno de los bordes de $B\backslash A$ $A$y mira si hay un ciclo en $A$. Si no se soluciona el problema, de lo contrario no es exactamente un ciclo en $A$. En este ciclo existe un borde $e$ que no está de $B$, de lo contrario un ciclo será también en $B$ lo cual es imposible, ya que $B$ es bosque. Retire $e$ $A$ y continuar desde el principio. Por lo que podemos sustituir todos los bordes en $A$ por los bordes en $B$.

Si no va a ser una ventaja en $B\backslash A$, que se contradice $|B| > |A|$, ya que el tamaño de $A$ no es cambiado.

Eso significa que no podemos seguir infinitamente, por lo que habrá un borde en $B\backslash A$ cuando se añade a $A$ no forma un ciclo.