# Forest graphs $F_1$ and $F_2$ with same vertices but different edges. Prove there is an edge where $F_1$ with it is still a forest

I am having quite a hard-time with this question, been thinking about it for a few hours and have not got a clue on how to even start proving this, because it is trivial but proving it has been hard for me.

Given two forests $F_1 = (V,A)$ and $F_2 = (V,B)$ with same vertices group $V$. It is also given that $|B| > |A|$. Prove: there exists an edge $e \in B \backslash A$ where $F_1 \cup \{e\}$ is still a forest.

Any help will be appreciated!

-
How exactly is it a subgraph? $|A|$ and $|B|$ can be much, much different. –  TheNotMe May 25 '13 at 11:38
You're right; I got carried away and read $|A|<|B|$ as $A\subset B$. –  Eric Stucky May 25 '13 at 11:41
Haha no worries :P –  TheNotMe May 25 '13 at 11:49

Add one edges from $B\backslash A$ to $A$ and look if there is a cycle in $A$. If there isn't the problem is solved, otherwise there is exactly one cycle in $A$. In that cycle exists en edge $e$ which is not from $B$, otherwise a cycle will be also in $B$ which is impossible, since $B$ is forest. Remove $e$ from $A$ and continue from beginning. So we can replace all edges in $A$ by edges in $B$.

If there will not be an edge in $B\backslash A$ that will contradict that $|B| > |A|$, since the size of $A$ is not changed.

That means we cant continue infinitely, so there will be an edge in $B\backslash A$ when adding it to $A$ will not form a cycle.

-
"otherwise there is exactly one cycle in $A$." Why? –  TheNotMe May 30 '13 at 7:38
–  Ashot May 30 '13 at 15:27

Hint: The fact that $|B|>|A|$ can be used to prove that $F_1$ is not connected. Why does this imply that such an edge exists?

Some more comments: This is an intermediate result; there is an important part of the argument that requires non-connectivity (or something equivalent) to make work.

Notice that in general there is no edge that makes $F_1$ connected. Even if there is, it might not be in $B$. But we are not looking for such an edge, simply one in $B$ which does not produce a cycle in $A$.

-
Correct me if I am wrong, isn't it enough to be given that a graph $G$ is a forest, for it not to be connected? –  TheNotMe May 25 '13 at 11:50
Usually, trees and forests are defined such that a tree is a connected forest, so that "forest" itself does not imply anything about connectedness. However, if your book or class has been following a different convention, it is of course important to follow that one. –  Eric Stucky May 25 '13 at 11:56
"Consider the set of edges $e$ such that $F_1'=(V,E\cup\{e\})$ is a forest…" ~ ~ [[note: I have removed my comments and incorporated them into the answer to keep the discussion abbreviated.]] –  Eric Stucky May 25 '13 at 12:25
What is $E$? Could you provide complete proof, or sketch of it. –  Ashot May 25 '13 at 12:31
Augh! When I wrote $E$, I meant the edge set $A$. I am sorry for all the confusion. I would rather not provide the complete proof yet: The OP has two ideas to run with now and since e seemed to be struggling with getting started, hopefully e can now get over those "first line" difficulties. I'd like to know what sort of progress e has made before giving more detailed advice. –  Eric Stucky May 25 '13 at 12:48