Adición de bordes a un bosque de otro bosque en el mismo gráfico

Question

Estoy teniendo problemas con esta pregunta:

Deje $G = (V,E)$ un gráfico. Deje $F$ $F'$ ser bosques en $G$ tal que $|F|< |F'|$ (donde $|F|$ indica el número de bordes de $F$). Mostrar que hay una ventaja $e$ $F'$ tal que $F \cup \{e\}$ es un bosque.

Sugerencia: Considerar un componente de $(V, F \cup F')$ $F'$ bordes de $F$.

No estoy seguro de cómo proceder con este como yo no tienen ejemplos de este tipo de problema. Se resolvió con una inducción argumento? O estoy pensando que tal vez usted tiene que demostrar que el número de aristas de $F'$ es mayor por lo que no es un extremo de una arista de $F'$ que no se puede incidente con un borde de $F$?

Estoy confundido, como el componente que se nos pide a considerar en la sugerencia podría ser 'desordenado' con los bordes de $F$ $F'$ completamente mezclado, siempre y cuando no hay ningún ciclo dentro de los subdiagramas de los bordes de $F$ o $F'$ (por lo que podría ser un ciclo con dos bordes de $F$ y uno de $F'$ por ejemplo).

Gracias

Answer 1

Seguir la pista. Supongamos que $E=F\cup F'$, e $E$ está conectado con $|F'|>|F|$.

Si $F$ es un árbol único que no puede ser máxima de otra manera $|F'| \le |F|$ por lo tanto usted puede encontrar un borde que no crea bucles en $F$ (en $F'$ porque $F'\cup F = E$) y usted puede agregar a $F$ a un bosque.

Si $F$ no está conectado tomar una trayectoria mínima que reduce el número de componentes conectados de $F$. Dicha ruta se compone de los bordes, que no están en $F$ por lo tanto están en $F'$. De nuevo la adición de cualquiera de los bordes de dicha ruta se obtiene el resultado.

Answer 2

Sugerencias:

1. Si $G = (V,E)$$|V| = n$$|F| = k$, a continuación, cómo muchos de los componentes conectados a ha $F$ en términos de$n$$k$?
2. Considere la posibilidad de un gráfico de $G'$ tal que tome $F'$ y el contrato de todos los vértices que pasa a estar en un solo componente conectado en $F$ ($F'$).
3. El uso de $(1)$, ¿cómo puede usted probar que $G'$ tiene que tener al menos un borde? El uso de $(2)$, ¿cómo puede usted probar que este borde no crea un ciclo en el $F$? Cómo podría llegar a la conclusión de que $F \cup \{e\}$ es todavía un bosque?

Buena suerte!

Answer 3

Si no hay ningún borde en$F'$ que se pueda agregar a$F$ sin crear un ciclo, entonces cualquier vértice conectado por un borde de$F'$ está conectado por$F$, y por lo tanto cualquier los vértices conectados por$F'$ están conectados por$F$. Para el componente considerado en la sugerencia, esto implica que su subgrafo formado por aristas de$F$ tiene como máximo tantos componentes y al menos tantos vértices como su subgrafo formado por aristas de$F'$. Por lo tanto, tiene al menos tantos bordes, una contradicción.