# 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

-

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.

-
Why is $|F'|\le|F|$ if $F$ is a single maximal tree? – joriki Mar 10 '13 at 14:03
Because a forest cannot have more edges than a maximal tree. – Emanuele Paolini Mar 10 '13 at 14:11

Hints:

1. If $G = (V,E)$ and $|V| = n$ and $|F| = k$ then how many connected components has $F$ in terms of $n$ and $k$?
2. 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'$).
3. 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!

-
What do you mean by "this edge does not create a cycle in $F$"? The edge is an edge of $G'$, which was created by contracting vertices in $F'$; in what sense is it or does it correspond to an edge that could be added to $F$? – joriki Mar 10 '13 at 14:06
@joriki Let $[v]$ be the abstract class of $v \in V$ in the relation of connectedness in $F$ (those are the vertices of $G'$). If $([v],[u])$ is an edge in $G'$ then there was at least one edge $(p,q) \in F' \subset E$ for some $p \in [v]$ and $q \in [u]$. So, by "to add $([v],[u])$ to $F$" I meant "to add $(p,q)$". I think this is clear enough (there are very few ways in which you could add an edge of $G'$ to $F$). – dtldarek Mar 10 '13 at 14:28

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.

-