1
$\begingroup$

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.

$\endgroup$
6
  • 1
    $\begingroup$ "Two unique" is an oxymoron. Unique means one. Google translate has failed you. Please rephrase. $\endgroup$
    – bof
    May 9 '21 at 13:03
  • 2
    $\begingroup$ Writing edge disjoint and vertex disjoint paths would be better I guess for parts 1 and 2, respectively. $\endgroup$
    – Snowball
    May 9 '21 at 13:15
  • 2
    $\begingroup$ 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$. $\endgroup$
    – Snowball
    May 9 '21 at 13:24
  • 2
    $\begingroup$ 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. $\endgroup$
    – Snowball
    May 9 '21 at 13:51
  • 2
    $\begingroup$ @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. $\endgroup$ May 9 '21 at 14:18
3
$\begingroup$

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

enter image description here

Thanks for the picture @user3733558

$\endgroup$
2
  • 1
    $\begingroup$ Awesome solution! $\endgroup$
    – Snowflake
    May 9 '21 at 15:18
  • 1
    $\begingroup$ Thank you both for the solution and the picture! $\endgroup$
    – OmerLerner
    May 10 '21 at 10:19

Your Answer

By clicking β€œPost Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.