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

[CGandC]

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.

 

[Office_Shredder]

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.

 

[CGandC]

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]

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.

 

[CGandC]

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]

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.

 

[CGandC]

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]

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.

 

[CGandC]

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]

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?

 

[CGandC]

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

 

[Office_Shredder]

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

 

[CGandC]

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]

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.

 

[CGandC]

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]

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]

For what it's worth, I think my last post finds the edge $u,w_2$