 #1
 200
 12
 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.
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.