# Show that a graph composed of two trees has two unique paths

Let T1 and T2 be two edge disjoint trees spanning on |V| = n nodes. The graph G = (V , T1 ∪ T2) so |T1 ∪ T2| = 2n-2 and each graph (V,Ti) is a tree.

I'm working on two proofs/disproofs for this graph:

1. There are two edge disjoint paths between each set of vertices

2. There are two vertex disjoint paths between each set of vertices(besides the first two)

The first proof seems simple: There are two trees, each one has a path from x to y since the trees are disjoint, and in the graph G there will be two paths that don't share the same edges.

However, I've been stuck working on a proof for the second problem and have several approaches:

• Let A be the path from x to y in T1. I can remove all of the vertices from G, but then I'm stuck with no way to prove that the graph is connected.
• Same thing goes for removing A and proving that G = (V\A, E) is a tree. We don't know how many edges we will remove.

This is for an assignment, so any advice that can help me prove or disprove this problem would be useful, since I'm stuck on this problem and not sure if my approach is correct or not.

• "Two unique" is an oxymoron. Unique means one. Google translate has failed you. Please rephrase.
– bof
May 9 '21 at 13:03
• Writing edge disjoint and vertex disjoint paths would be better I guess for parts 1 and 2, respectively. May 9 '21 at 13:15
• Second part does not seem correct to me. Consider trees $T_1 = v_1-v_2-v_3-v_4-v_5-v_6-v_7-v_8-v_9-v_{10}-v_{11}$ and $T_2 = v_1-v_3-v_5-v_2-v_4-v_6- v_8-v_{10}-v_7-v_9-v_{11}$. See that going from $i < 6$ to $j>6$ requires passing through 6 in both trees. Therefore, when you combine them, you will still have to pass through 6 to go from $i<6$ to $j>6$. May 9 '21 at 13:24
• My intuition is that since trees are not 2 vertex connected, you can fix one vertex and construct the tree such that vertices on the left has to pass through this vertex to reach vertices on the left. Then, construct 2 such trees and you will get counterexample for second part. May 9 '21 at 13:51
• @Snowball I was working on my own counter-example when I saw your comment pop up, so I took the liberty to draw your idea as well. Feel free to use these pictures in your final answer. May 9 '21 at 14:18

Counterexample: $$𝑇_1=𝑣_1−𝑣_2−𝑣_3−𝑣_4−𝑣_5−𝑣_6−𝑣_7−𝑣_8−𝑣_9−𝑣_{10}−𝑣_{11}$$ and $$𝑇_2=𝑣_1−𝑣_3−𝑣_5−𝑣_2−𝑣_4−𝑣_6−𝑣_8−𝑣_{10}−𝑣_7−𝑣_9−𝑣_{11}$$. All paths from $$v_i$$ to $$v_j$$ ($$i<6$$,$$j>6$$) has to pass through $$v_6$$.