Adding edges to a forest from another forest in the same graph I am having problems with this question:
Let $G = (V,E)$ be a graph. Let $F$ and $F'$ be forests in $G$ such that $|F|< |F'|$ (where $|F|$ indicates the number of edges of $F$). Show that there is an edge $e$ of $F'$ such that $F \cup \{e\}$ is a forest.
Hint: Consider a component of $(V, F \cup F')$ with more $F'$ edges than $F$.
I'm not sure how to proceed with this as I have no examples of this type of problem. Is it solved with an induction argument? Or I am thinking maybe you have to show that the number of edges of $F'$ is greater so that there is one endpoint of an edge from $F'$ that cannot be incident with an edge of $F$?
I am confused, as the component we are asked to consider in the hint could be 'messed up' with edges from $F$ and $F'$ completely mixed, as long as there is no cycle within the subgraphs of edges from $F$ or $F'$ (so there could be a cycle with two edges from $F$ and one from $F'$ for example).
Thank you
 A: Follow the hint. Suppose that $E=F\cup F'$, and  $E$ is connected with $|F'|>|F|$. 
If $F$ is a single tree it cannot be maximal otherwise $|F'| \le |F|$ hence you can find an edge which does not create loops in $F$ (which is in $F'$ because $F'\cup F = E$) and you can add it to $F$ to keep it a forest.
If $F$ is not connected take a minimal path which reduces the number of connected components of $F$. Such path is composed of edges which are not in $F$ hence are in $F'$. Again adding any of the edges of such path you get the result.
A: Hints:


*

*If $G = (V,E)$ and $|V| = n$ and $|F| = k$ then how many connected components has $F$ in terms of $n$ and $k$?

*Consider a graph $G'$ such that you take $F'$ and contract all the vertices that happens to be in a single connected component in $F$ (not $F'$).

*Using $(1)$, how could you prove that $G'$ has to have at least one edge? Using $(2)$, how could you prove that this edge does not create a cycle in $F$? How could you conclude that $F \cup \{e\}$ is still a forest?


Good luck!
A: If there's no edge in $F'$ that can be added to $F$ without creating a cycle, then any vertices connected by an edge of $F'$ are connected by $F$, and hence any vertices connected by $F'$ are connected by $F$. For the component considered in the hint, this implies that its subgraph formed by edges of $F$ has at most as many components and at least as many vertices as its subgraph formed by edges of $F'$. Hence it has at least as many edges, a contradiction.
