Is $F \cup E(F')$ a forest? How show? Teorem: Let $F$ and $F'$ forests with $V(F') \subseteq V(F)$. If for every pair of vertices $u,v$ in $F'$ we have that $u$ and $v$ belong to connected components differents of $F$ or $u$ and $v$ belong to connected components differents of $F'$, then $F \cup E(F')$ is a forest.
Follows the proof that I did:
Proof: The proof is by induction on $|E(F')|. $If $|E(F')| = 0$, then the theorem is valid, because $F$ is forest.
Now assume that $|E(F')| \geq 1$. Let $e \in E(F')$. Assume that $e = xy$. Consider $F_e' = F' - e$.
By inductive hypothesis, $F \cup E(F_e')$ is a forest.
Since the vertice $x$ is connected to the vertice $y$ by the edge $e$ in $F'$, then $x$ and $y$ are a same connected component of $F'$.
Therefore, $x$ and $y$ must be in differents connected components of $F$(By cause this affirmation of theorem: "for every pair of vertices $u,v$ in $F'$ we have that $u$ and $v$ belong to connected components differents of $F$ or $u$ and $v$ belong to connected components differents of $F'$").
Then add the edge $e$ in $F$ not creates cycle. Moreover, $F_e' \cup e$ is a forest, because $F'$ is a forest.
Then $x$ and $y$ are in connected component differents of $F\cup E(F'_e)$.
So, $F \cup E(F')$ is a forest.
This proof is correct? If no, why is wrong?
 A: Well, first of all, we know that the proof is wrong because the theorem is wrong. Let $F$ and $F'$ be forests on the vertices $\{a,b,c,d\}$ with $E(F) = \{ab, cd\}$ and $E(F') = \{bc, ad\}$. Then the conditions of the theorem are satisfied, but combining the two forests creates a cycle.
So what is going wrong in your proof? The problem is that when we add the edges of $F'$ to $F$ one at a time:

*

*To know that $e = xy$ will not create a cycle, you need to check that $x$ and $y$ are in different components of $F \cup E(F'_e)$.

*However, the condition in the theorem only tells us that $x$ and $y$ are in different components of $F$.

This might not be enough, and we can see this happening in your example. Starting with $F$, we add the first edge $bc$ to get a graph $G$ with edges $\{ab, bc, cd\}$. Now, when we try to add the edge $ad$, we have a problem: $a$ and $d$ are in the same component of $G$, even though they were in different components of $F$. (The edge $bc$ we added from $F'$ creates an $a-d$ path in $G$.) So we get a cycle.
