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.
Second part is not correct.
Intuition: 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 right. Then, construct 2 such trees and you will get counterexample for second part.
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$.
Thanks for the picture @user3733558