# Showing existence of an Edge s.t. Graphs T1' , T2' are Trees

Homework Statement:
Let ## G ## be a connected graph, simple and finite. Let ## T_1 = \langle V,E_1 \rangle ,\ T_2 = \langle V,E_2\rangle ## be trees s.t. ## E_1, E_2 \subseteq E ##. Show that for every edge ## e_1 \in E_1 \setminus E_2 ## there exists an edge ## e_2 \in E_2 \setminus E_1 ## s.t.
## T_1' = \langle V,(E_1\setminus \{ e_1 \}) \cup \{ e_2 \} \rangle ~~~~~## , ## T_2' = \langle V,(E_2\setminus \{ e_2 \}) \cup \{ e_1 \} \rangle ~~~~##, are both trees.
Relevant Equations:
Knowing definitions in graph theory: Trees, Simple circuits, Simple path, circuits, paths.
Attempt - I am stuck at this problem for hours, couldn't make any progress. Still, here's what I've done :
Let ## e_1 \in E_1 \setminus E_2 ## be arbitrary. Suppose for the sake of contradiction that ## \forall ## ## e_2 \in E_2 \setminus E_1 ##, ## T_1' = \langle V,(E_1\setminus \{ e_1 \}) \cup \{ e_2 \} \rangle ~~~ ## OR ## ~~~~ T_2' = \langle V,(E_2\setminus \{ e_2 \}) \cup \{ e_1 \} \rangle ## aren't trees.
Let ## e_2 \in E_2 \setminus E_1 ## be arbitrary, then ## T_1' = \langle V,(E_1\setminus \{ e_1 \}) \cup \{ e_2 \} \rangle ~~~ ## OR ## ~~~~ T_2' = \langle V,(E_2\setminus \{ e_2 \}) \cup \{ e_1 \} \rangle ## aren't trees. We'll show that ## T_1' ## is connected or has simple circuits and we'll also show that ## T_2' ## is connected or has simple circuits ( so that we'll reach contradiction for both ). [ From here I don't know what else to do ]

I feel lost. I think in my attempt I'm overcomplicating the proof and I'd very appreciate if you can please help me/give me a direction as to what I should do.

## Answers and Replies

Office_Shredder
Staff Emeritus
Science Advisor
Gold Member
I haven't fully though through the proof, but I think there are some simpler ideas that you can start with to at least get some intuition.

For example, if you take ##e_1## out of ##T_1##, then you split that tree into two disconnected trees. Claim: there must exist an edge in ##T_2## that joins these two groups together.

Let's say for intuition, ## T_1 ## looks like this:
where ## e_1 = \{ v ,u \} ##.
After taking the edge out of the graph we get two subtrees for ## T_1 ## which I denote ## T_1^{(a)} ## , ## T_1^{(b)} ##:

But I'm having difficulty seeing how ## T_2 ## plays a role here.

Office_Shredder
Staff Emeritus
Science Advisor
Gold Member
Does there have to be an edge in ##T_2## that connects a vertex in ##T_1^a## and ##T_1^b##? I think the answer is yes.

Ok, if ## e_1 = \{ u ,v \} \in E_1 \setminus E_2 ## note that ## u,v \in V##, In particular, these vertices exist in tree ## T_2 ##, hence there must exist a simple path between them in ## T_2 ##, meaning ## \langle u,w_1,...,w_k,v \rangle ## where ## w_1,...,w_k \in V ## .
But how can I use this simple path in order to show that there exist an edge ## \{ u, v \} \in E_2 ##?

Office_Shredder
Staff Emeritus
Science Advisor
Gold Member
The edge ##\{u,v\}## is not going to be in ##E_2##. There has to be some other edge in ##T_2## that spans the gap.

So I can look at the simple path ## \langle u,w_1,...,w_k,v \rangle ## from ## T_2 ##, take ## w_1,...,w_k ## and connect them to ## u,v ## in ## T_1 ## after the split, If I do this then I have necessarily bridged the gap that was split when I removed ## e_1 ## from ## T_1 ##. So although I may not have a single edge connecting ## u,v ## in ## T_1 ## again, I have a set of edges going from ## u ## to ## v ## in ## T_1 ##

Office_Shredder
Staff Emeritus
Science Advisor
Gold Member
Why are you connecting them to u and v? The only thing you are allowed to do is pick an edge from ##T_2##. So the edge you would add is going to be like, ##\{w_i, w_{i+1}\}## for some i.

Try actually drawing a ##T_2## and see if you can point at the right edge.

Yes you are right. Here's an example of what ## T_2 ## could look like

I'll pick edge ## { w_1,w_2} \in E_2 ## and add it to the gap after the split in ## T_1 ##, so ## T_1 ## would look like:

and we denote this new tree as ## T_1' ## , we do the same process to get ## T_2' ##

Office_Shredder
Staff Emeritus
Science Advisor
Gold Member
In your forest of ##T_1^a## and ##T_1^b## u and v both had degree one. You were then supposed to add an edge that did not connect u to v, so at least one of them should be a degree one vertex in ##T_1'##. Hence I think your picture can't be correct.

I'm not really sure how ##T_1## and ##T_2## are supposed to lay on top of each other, like which vertices in each graph match to which vertices on the other?

So ## T_1' ## ( after creating only one edge which leaves ## u ## with degree 1) should look like this?:

Office_Shredder
Staff Emeritus
Science Advisor
Gold Member
##w_1## there is a totally new vertex you just added to the picture. It has to be a vertex that already existed.

I think you should label every single vertex in the picture of ##T_1## and give the same labeling to the picture of ##T_2##. Then you can see where ##w_1## and ##w_2## actually are in the ##T_1## picture. You may or may not have picked the right edge, your picture so far is not sufficient to know if ##\{u,w_1\},\{w_1,w_2\}## or ##\{w_2,v\}## is the right edge.

Ok, I labeled the graphs:

I still don't fully see which edge I can take in ## T_2 ## that will connect me ## u,v ## After I split the edge between them in graph ## T_1 ##

Office_Shredder
Staff Emeritus
Science Advisor
Gold Member
When you remove ##u,v## from ##T_1##, to reconnect the trees you need to find an edge from the set ##(u,p_5,p_6)## to the set of the other vertices.

##p_5,p_2## would work. So would ##p_5,v##. So would ##u,w_2##. ##p_6,p_2## would also work.

The main point is that since ##T_2## is a tree, I claim there is at least one edge that connects these two groups of vertices.

Ok I think I got the intuition, here's an example of what ## T_1' ## could be based on the last two images above:

Maybe the proof should be something like:
Let ## e_1 \in E_1 \setminus E_2 ##. Meaning there exist ## u,v \in V ## s.t. ## e_1 = \{ u,v \} ##. since ## e_1 \notin E_2 ## and ## T_2 ## is a tree hence there exists a simple path ## \langle u,w_1,...,w_k,v \rangle## in ## T_2 ##. Remove ## e_1 ## from ## T_1 ##, we'll get two subtrees which we denote as ## T_1^{a} ##, ## T_1^{b} ## and the whole forest denote as ## T_1^{''} ##. Choose in ## \langle u,w_1,...,w_k,v \rangle ## a vertex that has no path to ## v ## or ## u ##. Suppose we chose a vertex that has no path to ## u ## and we denote it as ## \tilde{w} ##. We'll Choose an edge from ## \tilde{w} ## to another vertex that has a path to ## u ## that we denote as ## \tau ## s.t. ## \{ \tilde{w}, \tau \} \in E_2 ##. Create the edge in ## T_1^{''} ## , now ## T_1^{''} ## is not a forest but a tree since ## T_1^{a} , T_1^{b} ## are connected, denote this tree as ## T_1^{'} ##. We similarly prove existence of ## T_2^{'} ##, and so we're finished.

Is the proof above ok?, if not ,I don't really know how to prove the theorem that there must exist an edge in ## T_2 ## that will connect the two disconnected components in ## T_1^{''} ##. Do you have an Idea as to what I should do?

Office_Shredder
Staff Emeritus
Science Advisor
Gold Member
Choose in ## \langle u,w_1,...,w_k,v \rangle ## a vertex that has no path to ## v ## or ## u ##. Suppose we chose a vertex that has no path to ## u ## and we denote it as ## \tilde{w} ##. We'll Choose an edge from ## \tilde{w} ## to another vertex that has a path to ## u ## that we denote as ## \tau ## s.t. ## \{ \tilde{w}, \tau \} \in E_2 ##.

I don't really understand what these are trying to say, but I would word it like this. The path ##\left<u,w_1,...,w_n,v\right>## in ##T_2## starts with a vertex in ##T_1^a## and ends with a vertex in ##T_1^b##. Hence it must have an edge that starts with a vertex in ##T_1^a## and ends with a vertex in ##T_1^b##, since every edge that starts in ##T_1^a## ends in either ##T_1^a## or ##T_1^b##, and if no edge starts in ##T_1^a## and ends in ##T_1^b##, then ##u\in T_1^a## implies ##w_1\in T_1^a##, which then implies ##w_2\in T_1^a##, all the way up to ##v\in T_1^a##. But ##v## is actually in ##T_1^b##.

CGandC
Ok thanks, I think I have to think about the problem more in order for it to fully sink in.

Office_Shredder
Staff Emeritus
Science Advisor
Gold Member
For what it's worth, I think my last post finds the edge ##u,w_2##