Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
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 comment

2 Answers

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.

share|improve this answer
    
"otherwise there is exactly one cycle in $A$." Why? –  TheNotMe May 30 '13 at 7:38
1  
add comment

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$.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.